利用“百钱买百鸡”探讨穷举法
利用“百钱买百鸡”探讨穷举法
山东省鱼台县第一中学范海涛2009年7月23日16:35 浏览：97 专家浏览：0 | 评论：10 专家评论：0
利用“百钱买百鸡”探讨穷举法
【课标要求】
（1）了解穷举法的基本概念及用穷举法设计算法的基本过程。
（2）能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。
【教材处理】
由于这是学生首次接触用非解析法解题，如果要求学生很快掌握其基本过程并且能对算法进行优化，将是不现实的。尤其是考虑到学生的信息技术基础参差不齐，可能差距较大，基础差的学生在可能不能接受太多的内容；而且，就算能“吸收”到全部内容，未必就能全部“消化”。
本节课选取来自《张邱建算经》的百钱买百鸡问题作为本次教学的主题。这样既能提高学生学习的兴趣，又能使学生容易掌握知识，还可以培养学生的民族自豪感和通过建立数学模型和设计程序解决实际问题的习惯。
【学生情况分析】
1、学生在本节课前学习高中信息技术新课程的《算法与程序设计》模块已经有一段时间了，学生对算法和程序设计有了一定的认识，但是在面对实际问题时如何设计算法并且用程序实现算法来解决问题上，尤其是对于无法用解析法解决或者是用解析法解决比较困难的问题如何设计算法还是没有什么思路；
2、“百钱买百鸡”问题的数学模型是解不定方程，学生在初中的数学课上学过。本次课在原有知识的基础上，通过对实际问题的分析找到合适的数学模型，使学生基本理解和掌握穷举法解题的思路；
【教学目标】
1、知识与技能
（1）了解非解析法解题的基本思路；
（2）理解和掌握穷举法解题的思路，
2、过程与方法
经历分析问题、建立数学模型、编写和调试程序，得到最终结果的过程，理解和掌握用穷举法解题的基本思路与过程；
3、情感态度与价值观
（1）通过主题任务的完成，激发民族自豪感和自身的成就感；
（2）通过小组讨论与探究活动，提高团队合作能力，促进探究的热情；
（3）通过结合学习生活的实际例子，进一步提高利用信息技术解决学习、生活问题的能力。【教学重点与难点】
重点：用穷举法解题的基本思路和过程
难点：分析问题建立数学模型，构造算法
【教学策略】
教学理念与方法：以培养学生的信息素养为前提，遵循“学生是学习的主体，教师是学习的指导者”的新课程教学理念，根据本节课中各个知识点的联系，采用了“主题任务”的教学模式，通过任务驱动法，利用多媒体教学系统和投影设备，使学生在任务中学习，在实践中探究，在探究中总结归纳知识规律和方法，加强知识的实际应用。
【教学设计提要】
1、以解决简单的“百钱买百鸡”问题为切入点，引导学生思考采用新的算法；
2、通过分析“百钱买百鸡”问题、带出“穷举法解决问题”这一教学重点，并通过老师演示、上机实践和探究讨论，使学生的学习兴趣得到提升，因此可以较容易的接受和掌握重点内容。
3、主题任务解决后，拓展思路，并结合上机实践、合作探究等形式，让学生大胆想像，提出创新观点，并进行归纳总结，体现新课标中“学生是学习的主体”这一教学理念。
4、老师总结本节课的学习内容，帮助学生理清思路，启发学生运用信息技术来解决学习和生活问题，并通过布置课后练习，引导学生思考穷举法的另一个主要方面——算法的优化。【学生活动设计】
本节课中根据主题的任务为学生设计了自主活动（上机实践操作）、师生活动（多次个别提问与交流）、生生活动（讨论与交流、个别学生上台演示）、小组活动（讨论、合作探究问题）等多种的活动情境。这些活动使整个课堂的气氛活跃起来，使学生真正成为学习的主人，让学生在活动的过程当中学会观察，学会思考，学会讨论，学会与别人合作交流，进一步提高自主学习、合作学习、探究学习的能力。
【教学媒体】
多媒体课件、多媒体教学系统、网络课堂网站
【教学过程】
教学内容教师活动学生活动设计意图
一、创设情境，导入主题
讲述神童张邱建巧妙解决百钱买百鸡问题的故事，并让学生讨论如果自己是张邱建将如何解题。学生各自说出自己的意见和例子。这个故事在学生的民族自豪感的同时，可以激起青年学生的好胜心，并且有合适的数学模型。
这类问题还有很多，如和尚分馒头等，它们都有什么共同点？我们是否可以用计算机来解决这类问题？分组讨论
二、建立数学模型题目原来的表达方式不便于用计算机解题、我们要把它改写成便于计算机解决的数学语言，也就是建立数学模型。学生分析问题，发现这些问题都可以归结为数学上的解不定方程组。从简单情况开始，循序渐进，使学生有成功感。遇到稍深一些的情况时，引导学生利用旧知识去解决问题，使他们更好地理解分类汇总的步骤和基本原理。
三、设计算法
既然已经将问题归结为解不定方程组，那么用什么算法来解这个问题呢，用解析法可以吗？
能找到符合要求的情况的范围吗？
我们是否可以利用计算机高速运算的特点、把所有可能的情况列出来一一判断，找出符合条件的解？
答：不行，没有可以直接计算得到结果的公式
答：可以公鸡、母鸡、小鸡只数都是正整数，而且都不可能超过100，
答：可以，让代表鸡的只数的三个变量从1到100循环，在循环内用if语句判断鸡的总只数和钱数是否都是100。
当遇到困难问题时，及时引入新知识来解决，使学生很自然地接受新知识，并产生应用的兴
趣。
任务1：设计算法
这种算法称作穷举法，可以说是所有非解析法解题算法的基础。
学生将算法具体化、可以使用伪代码或流程图。
学生说明自己的算法。
四、程序实现，加强认识
任务2：在VB平台上实现自己的算法。
巡视学生，即时反映学生遇到的问题，引导正确做法。
学生运用刚学的知识来解决主题问题。
遇到问题无法解决的同学经老师点拨，马上改正错误。
学生演示自己的程序。
有了印象，学生通过实践掌握新知识的应用。
容易出错的地方能即时发现，及时改正，正确认识。
五、巩固练习
任务3：下面算式中每个字母代表一个不同的十进制数字，请找出这个算式。
ONE
+ ONE
= TWO
老师巡视，即时了解学生讨论的情况，作出指导。
形成小组探究问题，通过亲自动手验证讨论结果。
虽然不是不定方程，但很明显可以使用穷举法，一般初学者会对5个字母穷举，运算量比较大要105次循环。如果将三位数ONE作为穷举对象则只要500次循环。为算法的优化埋下伏笔。
六、拓展思路，提高理解
任务4：新娘和新郎
三对情侣参加婚礼，三个新郞为A、B、C，三个新娘为X、Y、Z。有人不知道谁和谁结婚，于是询问了六位新人中的三位，但听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。
教师引导学生考虑将题目的表述进行转换。
学生思考，再次遇到困难。题目不像前面有明显的穷举方式。
将A、B、C三人用1,2，3表示，将X和A结婚表示为“X=1”，将Y不与A结婚表示为“Y<>1”。按照题目中的叙述可以写出表达式：
x<>1 A不与X结婚
x<>3 X的未婚夫不是C
z<>3 C不与Z结婚
题意还隐含着X、Y、Z三个新娘不能结为配偶，则有：
x<>y且x<>z且y<>z 进一步加强对建模的理解，拓展思路。
七、小结和学生一起总结穷举法解决问题的思路和过程。归纳、简述穷举法解决问题的思路和过程。巩固知识和方法，把知识系统化、结构化。
八、布置任务，引申悬念穷举法是非解析法解题的基本方法、但是很多问题的规模很大、穷举法虽然在理论上可以找到解，但是需要的运算时间太长（以深蓝的棋谱数据为例）。所以要研究如何缩小穷举的规模。
查看有关国际象棋程序发展的网页以及其他有关网页、理解优化算法的必要性。
课后思考：检查已经自己的算法，看看有无办法优化。在课堂的结尾把下节课的内容作简要的铺垫，承上启下，使学生产生悬念，再次激起学生学习的兴趣，便于课后对知识继续进行探究和学习。
点评：这是一节比较标准的算法与程序实现教学课，通过分析学生的认知水平，以“百钱买百鸡”问题为切入点，使学生在原有基础上进一步体验算法思想。
教学中突出新课标对本节课的要求：
（1）了解穷举法的基本概念及用穷举法设计算法的基本过程。
（2）能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。围绕主题任务组织学生实施自主学习、探究学习和合作学习，充分体现新课标的倡导的学习方法，通过开展上机实践、小组讨论等活动较好的体现新课标精神，提高学生的参与性和学习欲望。
PYTHON中百钱买百鸡问题
PYTHON中百钱买百鸡问题 问题： 中国古代数学家张丘建在他的《算经》中提出了一个著名的“百钱买百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问翁、母、雏各几何？在PYTHON中编程实现将所有可能的方案输出。 问题分析： 根据题意设公鸡、母鸡和雏鸡分别为cock，hen和biddy，如果100钱全买公鸡，那么最多能买20只，所以cock的范围是大小等于0小于等于20；如果全买母鸡那么最多能买33只，所以hen的范围是大于等于0小于等于33；如果100钱全买小鸡，那么根据题意最多能买99只（小鸡的数量应小于100且是3的倍数）。在确定了各种鸡的范围后进行穷举并判断，判断的条件有以下3种：（1）、所买的三种鸡的钱数总和为100； （2）、所买的三种鸡的数量之和为100； （3）、所买的小鸡的数量必须是3的倍数。 程序代码： for cock in range(0,20+1): #鸡翁范围在0到20之间 for hen in range(0,33+1): #鸡母范围在0到33之间 for biddy in range(3,99+1): #鸡雏范围在3到99之间 if (5*cock+3*hen+biddy/3)==100:#判断钱数是否等于100 if (cock+hen+biddy)==100: #判断购买的鸡数是否等于100 if biddy%3==0: #判断鸡雏数是否能被3整除 print ("鸡翁:",cock,"鸡母:",hen,"鸡雏:",biddy) #输出程序运行结果： 鸡翁: 0 鸡母: 25 鸡雏: 75 鸡翁: 4 鸡母: 18 鸡雏: 78 鸡翁: 8 鸡母: 11 鸡雏: 81 鸡翁: 12 鸡母: 4 鸡雏: 84
百鸡百钱问题及其算法分析
百钱百鸡问题的最佳解决方案 （陕西师范大学计算机科学学院10级计科一班西安710062） 摘要：本文主要讨论百鸡百钱问题，通常用蛮力法策略，用枚举法表现，排除明显不合理情况，列举出符合问题的解，分别验证解的可行性，得到最优算法。 关键词：蛮力法；枚举；百鸡百钱； The money the chicken question the best solution duan xi-juan, zhongmei, zhao shan-shan, zhao ya-wen (School of Computer Science, ,Shanxi Normol University, Xi’an 710062) Abstact :In this article, we mainly discuss the chicken and the money problem. Usually use brute force method strategy, with enumeration method performance, eliminate obviously unreasonable situation, Enumerate conform to the problem solution, which verified the feasibility of the solution, and get the optimal algorithm. Keywords: The brute force method;Enumeration;Hundred chickens money 1引言 在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。 2问题描述 百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了他的著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？ 3算法设计 根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不会理的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。 1）算法设计一 首先问题有三种不同的鸡，那么我们可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买鸡翁最多可以买100／5=20只，显然
著名数学难题赏析-百钱百鸡
------著名数学难题赏析： 百鸡百钱 数学教研组 （共两课时120分钟） 我国古代数学书《张邱建算经》中有如下问题，也就是著名的百鸡百钱问题。大意是：公鸡1只值钱5，母鸡1只值钱3，小鸡3只值钱1。今有钱100，买鸡100只。问公鸡、母鸡、小鸡各买几只？ 关于这个“百鸡百钱问题”还流传着下面一个故事哩！ 在我国南北朝的时候，京城里有个卖鸡的张老老，所生一子，天资聪颖，勤学不怠。到十二三岁，已经博览群书，尤其富有算术的天才。邻居每遇疑难问题，或是钱银上发生纠纷，都由他一言解决。因此大家都叫他张神童，逐渐传扬开去，不久就远近闻名了。当朝的老丞相爱才若渴，一天，听人谈到张神童的算法，心中很是不信，当下想了一个方法要去试探他，于是唤他的仆人去打听张老老卖的鸡是什么价钱。不多时仆人回答说：“公鸡每只卖钱五文，母鸡每只卖钱三文，小鸡每三只卖钱一文。”老丞相就拿出一百文钱，命仆人去给张老老，叫他尽这一百文钱把三种鸡配成一百只，不多不少，明天送来。张老老暗想：这实在是一个难题，然而又不敢违命，当时只好一口答应。等到收市后，就开始把三种鸡配起来。但是左配右配，总是配不成。正在无计可施的时候，他的儿子来了，问起情由，才知道是这样的一件事。于是安慰着父亲，叫他不要着急，明天总有办法。张神童当晚经过仔细研究，果然找到了答案。第二天选出了“公鸡4只，母鸡18只，小鸡78只”叫他父亲送到相府。老丞相拿来一算：4只公鸡值钱二十文，18只母鸡值钱五十四文，78只小鸡值钱二十六文，共计100只鸡，恰巧值钱一百文。心里一高兴，立刻又拿一百文钱给张老老，叫他明天再送一百只鸡来，不过三种鸡的只数要换一种方法搭配。张老老口头答应着，心里很是担忧，垂头丧气地回到家，忙和儿子商量。儿子说：“你明天拿8只公鸡，11只母鸡，81只小鸡送去就是了。”第二天张老老依言送去，老丞相一算，又是一点不错。心里一高兴，又给张老老一百文钱，要再另配一百只鸡。张老老暗想：这回恐怕是无法应付了。不料他的儿子又检出“公鸡12只，母鸡4只，小鸡84只”叫父亲送
百钱买百鸡问题
百钱买百鸡问题 例9-8 百钱买百鸡问题——一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少）。 这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x ，y ，z ，问题化为三元一次方程组： ? ? ?=++=++)(100) (1003/35百鸡百钱z y x z y x 这里x,y,z 为正整数，且z 是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z 的取值范围： 1) x 的取值范围为1～20 2) y 的取值范围为1～33 3) z 的取值范围为3～99，步长为3 对于这个问题我们可以用穷举的方法，遍历x,y,z 的所有可能组合，最后得到问题的解。 数据要求 问题中的常量： 无 问题的输入： 无 问题的输出： int x ，y ，z /*公鸡、母鸡、小鸡的只数*/ 初始算法 1．初始化为1； 2．计算x 循环，找到公鸡的只数； 3．计算y 循环，找到母鸡的只数； 4．计算z 循环，找到小鸡的只数； 5．结束，程序输出结果后退出。 算法细化 算法的步骤1实际上是分散在程序之中的，由于用的是for 循环，很方便的初始条件放到了表达式之中了。 步骤2和3是按照步长1去寻找公鸡和母鸡的个数。 步骤4的细化 4．1 z ＝1 4．2 是否满足百钱，百鸡 4．2．1 满足，输出最终百钱买到的百鸡的结果 4．2．2 不满足，不做处理 4．3 变量增加，这里注意步长为3 流程图
图5-8 程序执行流程图 程序代码如下 #include "stdio.h" main() { int x,y,z; for(x=1;x<=20;x++) { for(y=1;y<=33;y++) { for(z=3;z<=99;z+=3) { if((5*x+3*y+z/3==100)&&(x+y+z==100))/*是否满足百钱和百鸡的条件*/ printf("cock=%d,hen=%d,chicken=%d\n",x,y,z); } } } } 分析
c语言百钱买百鸡问题
百钱买百鸡问题——一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少）。 这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x ，y ，z ，问题化为三元一次方程组： ? ? ?=++=++)(100) (1003/35百鸡百钱z y x z y x 这里x,y,z 为正整数，且z 是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z 的取值范围： 1) x 的取值范围为1～20 2) y 的取值范围为1～33 3) z 的取值范围为3～99，步长为3 对于这个问题我们可以用穷举的方法，遍历x,y,z 的所有可能组合，最后得到问题的解。 数据要求 问题中的常量： 无 问题的输入： 无 问题的输出： int x ，y ，z /*公鸡、母鸡、小鸡的只数*/ 初始算法 1．初始化为1； 2．计算x 循环，找到公鸡的只数； 3．计算y 循环，找到母鸡的只数； 4．计算z 循环，找到小鸡的只数； 5．结束，程序输出结果后退出。 算法细化 算法的步骤1实际上是分散在程序之中的，由于用的是for 循环，很方便的初始条件放到了表达式之中了。 步骤2和3是按照步长1去寻找公鸡和母鸡的个数。 步骤4的细化 4．1 z ＝1 4．2 是否满足百钱，百鸡 4．2．1 满足，输出最终百钱买到的百鸡的结果 4．2．2 不满足，不做处理 4．3 变量增加，这里注意步长为3 流程图
图5-8 程序执行流程图 程序代码如下 #include "stdio.h" main() { int x,y,z; for(x=1;x<=20;x++) for(y=1;y<=33;y++) for(z=3;z<=99;z+=3) { if((5*x+3*y+z/3==100)&&(x+y+z==100))/*是否满足百钱和百鸡的条件*/ printf("cock=%d,hen=%d,chicken=%d\n",x,y,z); } } 分析 程序运行结果如下： cock=4,hen=8,chicken=78 cock=8,hen=11,chicken=81 cock=12,hen=4,chicken=84
多种解法求百钱百鸡问题
学号：0121210680225 《算法设计与分析B》大作业 题目多种解法求百钱百鸡问题 学院计算机科学与技术学院 专业软件工程 班级Sy1201 姓名李安福 指导教师何九周 2014 年12 月26 日
多种解法求百钱百鸡问题 摘要：中国古代数学家张丘建提出的“百钱买百鸡”可以采用蛮力法来解决。本文给出 了百钱百鸡问题的描述，采用蛮力法来解决这个问题，并通过分析对算法进行了优化，进一步提高了解决此问题的效率。 关键字：枚举，执行效率，蛮力法，不定方程，循环变量。 1引言 蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概 念定义。 这种方法经过很少的思考，把问题的所有情况或所有的过程交给计算机去一一尝试，从中找出问题的解。由于计算机运算速度快，在解决问题时可采用这种“懒惰”的策略。蛮力法的主要优点在于它是有广泛的适用性和简单性；它的缺点是大多数蛮力算法的效率都不高。 2问题概述 百钱百鸡问题: 中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ 3问题的分析 题目分析与算法设计 这是一个古典数学问题我们假设公鸡、母鸡和小鸡的个数分别为x,y,z,那么买公鸡的钱数为5x ，买母鸡的钱数为3y ，买小鸡的钱数为z/3；再由题意，x,y 和z 的和为100，问题化为可三元一次方程组，该问题的数学模型如下： ?? ?=++=++)(100)(1003/35百鸡百钱z y x z y x 这里x,y,z 为正整数，且z 是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z 的取值范围： 1) x 的取值范围为1～20 2) y 的取值范围为1～33 3) z 的取值范围为1～99 对于这个问题我们可以用穷举的方法，遍历x,y,z 的所有可能组合，最后得到问题的解。 4算法设计 4.1算法设计1 4.1.1数据要求 问题中的常量： 无
java程序”百钱买百鸡“
尝试分别用三层循环、两层循环、一层循环编程实现“百钱买百鸡”问题。母鸡5分钱一只，公鸡三分钱一只，小鸡一分钱三只，现在有百钱欲买百鸡，有多少种买法？ 三层循环 //百钱买百鸡-三层循环 //母鸡5分钱一只，公鸡三分钱一只，小鸡一分钱三只 //母鸡m只，公鸡n只，小鸡k只 public class BaiQianMaiBaiJi3 { public static void main(String[] args) { int m,n,k,i=0; for(m=0;m<=20;m++) for(n=0;n<=33;n++) for(k=0;k<=300;k+=3) if(5*m+3*n+k/3==100&&m+n+k==100) i++; System.out.println("百钱买百鸡共有 "+i+" 种方法"); } } 两层循环 //百钱买百鸡-两层循环 //母鸡5分钱一只，公鸡三分钱一只，小鸡一分钱三只 //母鸡m只，公鸡n只 public class BaiQianMaiBaiJi2 { public static void main(String[] args) { int m,n,i=0; for(m=0;m<=20;m++) for(n=0;n<=33;n++) if(5*m+3*n<=100&&m+n+(100-5*m-3*n)*3==100) i++; System.out.println("百钱买百鸡共有 "+i+" 种方法"); } } 一层循环 //百钱买百鸡-一层循环 //母鸡5分钱一只，公鸡三分钱一只，小鸡一分钱三只
//母鸡m只，公鸡n只，小鸡k只 4m+2n=2(k/3);m+n+k=100 public class BaiQianMaiBaiJi1 { public static void main(String[] args) { int m,i=0; for(m=0;m<=20;m++) { if((100-7*m)>0&&(100-7*m)%4==0)//&&k=3(100+m)/4,(100+m)%4==0 i++; } System.out.print("百钱买百鸡共有 "+i+" 种方法"); } }
百钱百鸡问题
百钱百鸡问题 我国古代数学家张丘建在《算经》中提出了著名的“百钱百鸡问题”：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？”意思是说：一只公鸡卖5枚钱，一只母鸡卖3枚钱，三只小鸡卖1枚钱，用100枚钱买100只鸡，能买到公鸡、母鸡、小鸡各多少只？ 分析： ① 这是一个不定方程问题。有3个未知数，2个方程：设公鸡、母鸡、小鸡数分别为i、j、k，则有i+j+k=100，i*5+j*3+k/3=100。需要让计算机去一一测试是否符合条件，找出所有可能的答案。由于价格的限制，如果只是一种鸡，则公鸡最多为19只（由于共100只鸡的限制，不能等于20只），母鸡最多33只，小鸡最多99只。 ② 这里用到的是穷举算法。穷举算法的基本思想是：对问题的所有可能答案一一测试，直到找到正确答案或测试完全部可能的答案。 程序如下： main( ) { int i,j,k; for(i=1;i<=19;i++) for(j=1;j<=33;j++) for(k=3;k<=99;k=k+3) { if((i+j+k==100)&&(i*5+j*3+k/3==100)) printf("i=%d,j=%d,k=%d\n",i,j,k); } } 运行结果为： i=4,j=18,k=78 i=8,j=11,k=81 i=12,j=4,k=84 #include
百鸡百钱——程序设计
深圳大学实验报告课程名称：高级程序语言设计 实验项目名称：“百钱买鸡问题”学院：信息工程学院 专业： 指导教师： 报告人：学号：班级： 实验时间： 实验报告提交时间： 教务处制
实验目的与要求： “百钱买鸡问题”： 设1个公鸡值5钱，1个母鸡值3钱，3个小鸡值1钱，现用100钱来买鸡，问有多少种方法买鸡？ （每种方法需包含公鸡、母鸡、小鸡的个数）。 编写一个程序，输出每一种方法的公鸡、母鸡、小鸡个数，并且统计出有多少种方法。要求：流程图、代码、结果、分析。 程序代码： #include
流程图： 数据处理分析： 设一百只鸡中公鸡、母鸡、小鸡分别为 i,j,k 问题化为三元一次方程组： 这里 i,j,k 为正整数，且k是3的倍数；由于鸡和钱的总数都是100，可以确定i,j,k 的取值范围： 1)i的取值范围为0～20 2)j的取值范围为0～33 3)k的取值范围为0～300，步长为3 对于这个问题我们可以用列举的方法得出i,j,k的所有可能组合，最后得到问题的解。（int i,j,k ,n=0; /*公鸡、母鸡、小鸡的只数、方法数*/） 初始算法 1．初始化为1； 2．计算i循环，找到公鸡的只数； 3．计算j循环，找到母鸡的只数； 4．计算k循环，找到小鸡的只数； 5．结束，程序输出结果后退出。 算法细化 算法的步骤1实际上是分散在程序之中的，由于用的是for循环，很方便的初始条件放到了表达式之中了。步骤2和3是按照步长1去寻找公鸡和母鸡的个数。
c++、python、vb求解百钱百鸡问题
我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题，该问题叙述如下：鸡翁一，值钱三；鸡母一，值钱二；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？ 翻译过来，意思是公鸡一个三块钱，母鸡一个二块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？ 题目分析 如果用数学的方法解决百钱买百鸡问题，可将该问题抽象成方程式组。设公鸡x 只，母鸡y 只，小鸡z 只，得到以下方程式组： A：3x+2y+1/3z = 100 B：x+y+z = 100 C：0 <= x <= 100 D：0 <= y <= 100 E：0 <= z <= 100 如果用解方程的方式解这道题需要进行多次猜解，因此我们用穷举法的方式来解题。 1.C++语言 #include if (3*i+2*j+k/3==100) and (i+j+k==100) and (k%3==0): print(i,j,k) 3.VB语言 Dim a As Integer, b As Integer, c As Integer For a = 0 To 33 For b = 0 To 50 For c = 0 To 100 If 3 * a + 2 * b + 1 / 3 * c = 100 And a + b + c = 100 Then Print "公鸡" & a, "母鸡" & b, "小鸡" & c End If Next c Next b Next a 一、题目描述 我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题，该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？ 翻译过来，意思是公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？ 二、解题思路 对n=100的情况，因为有三个变量，则有三重循环和二重循环两种算法 1、算法一：三重循环 （1）变量变化范围的确定：由于公鸡5钱一只，则100钱最多可购买100/5=20只公鸡，此即为第一个变量的变化上限；由于母鸡3钱一只，则100钱最多可购买100/3≈33只母鸡，此即为第二个变量的变化上限；由于小鸡三只一钱，而所有鸡的总数不得超过100只，则100即为第三个变量的变化上限； （2）条件的控制:由百钱买百鸡可知，鸡的数量为100只，买鸡所用的钱数为100钱，即控制条件为a+b+c=100且a*5+b*3+c/3=100; 2、二重循环： （1）变量变化范围的确定：由于整题共有3个变量，所以当前两个变量确定后，第三个变量自然被确定下来，故可采用二重循环解题。前两个变量的确定同三重循环，第三个变量则用c=n-a-b来确定； （2）条件的控制:由百钱买百鸡可知，鸡的数量为100只，买鸡所用的钱数为100钱，即控制条件为a+b+c=100且a*5+b*3+c/3=100; 由于需要讨论算法的时间性能，在程序中加入时间函数计算程序运行所需的时间进行比较。用控制变量的方法，对两种算法中的n进行同样的变化处理，来讨论两种算法的时间性能，e.g.分别令n=100,n=200,n=500,n=1000,n=2000,n=5000 三、自我评估、反思 由于较长时间未使用C语言编程，所以在使用语法上略显生疏了些，通过这次作业的实践过程，对C语言的编程语法规则熟悉了许多，虽然在运行过程中出现了一些错误，但也都能够较快地解决，第一次的数据结构实验作业总体完成的还算比较顺利。 个人认为我还需要更多的练习以熟悉数据结构的实验操作，争取在下次的实验中更加熟练，有效率。 四、实验结果截图 1、算法一：三重循环 （1）n=100 百钱百鸡问题 中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ *题目分析与算法设计 设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程： 5x+3y+z/3=100 x+y+z=100 所以此问题可归结为求这个不定方程的整数解。 由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。 *程序说明与注释 #include void main() { int x,y,z,j=0; printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\n"); for(x=0;x<=20;x++) /*外层循环控制鸡翁数*/ for(y=0;y<=33;y++) /*内层循环控制鸡母数y在0~33变化*/ { z=100-x-y; /*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/ if(z%3==0&&5*x+3*y+z/3==100) /*验证取z值的合理性及得到一组解的合理性*/ printf("%2d:cock=%2d hen=%2d chicken=%2d\n",++j,x,y,z); } } *运行结果 Follwing are possible plans to buy 100 fowls with 100 Yuan. 1:cock=0 hen=25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=84 *总是的进一步讨论 这类求解不定方程总理的实现，各层循环的控制变量直接与方程未知数有关，且采用对未知数的取值范上穷举和组合的方法来复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数，提高程序的执行效率，请读者考虑。 百鸡百钱问题 摘要: 本次报告主要讨论百鸡百钱问题，通常使用蛮力法策略，用枚举法来表现，列举出满足问题条件的解，排除一些明显不合理情况，分别验证解的可行性，得到最优算法。 关键词：蛮力法；枚举法；百鸡百钱； Hundred chickens money Abstract: This paper reports hundred chickens money, u sually using a brute force method strategy, use enumeration method to the performance, meet the conditions listed problem solution, exclude some obvious unreasonablesituation, respectively, to verify the feasibility of the solution, optimal algorithm. Key words: the brute force method; enumeration; hundred chickens money; 1 引言 在求解一个较小规模的问题时，可以根据问题中的约束条件把可能的情况一一列举出来，然后注意尝试从中找到满足约束条件的解，若该问题规模较大，符合条件的情况很多，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。 2 问题概述 公元前5世纪，我国古代数学家张丘建在他的《算经》中提出了著名的百鸡百钱问题“鸡翁一，值钱五；鸡母一，值钱三；鸡雏一，值钱一；百钱买百鸡，鸡翁，母，雏各几何？” 3算法设计 根据问题中的约束条件将可能的情况一一列举出来，但如果情况很多，排除一些明显的不会理的情况，尽可能减少问题可能解的列举数目，然后找出满足问题条件的解。 完成百鸡百钱问题的常规算法（懒惰枚举）的实现和改进算法（非懒惰枚举）的实现，以实验方法证明对于同一问题可以有不同的枚举范围，不同的枚举对象，解决问题的效益差别会很大。 算法设计一 懒惰枚举法：首先问题有三种不同的鸡，那么我们可以设鸡翁为x只，鸡母为y只，鸡雏为z只。由题意给出一共要用100钱买一百只鸡，如果我们全部买鸡翁最多可以买100/5=20只，显然x的取值范围是1~20之间；如果全部买鸡母最多可以买100/3=33只，显然y的取值范围在1~33之间；如果全部买鸡雏最多可以买100*3=300只，可是题目规定是买100只，所以z的取值范围是1~100.那么约束条件为：x+y+z=100且5*x+3*y+z/3=100。 流程图如下所示： 利用“百钱买百鸡”探讨穷举法 山东省鱼台县第一中学范海涛2009年7月23日16:35 浏览：97 专家浏览：0 | 评论：10 专家评论：0 利用“百钱买百鸡”探讨穷举法 【课标要求】 （1）了解穷举法的基本概念及用穷举法设计算法的基本过程。 （2）能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。 【教材处理】 由于这是学生首次接触用非解析法解题，如果要求学生很快掌握其基本过程并且能对算法进行优化，将是不现实的。尤其是考虑到学生的信息技术基础参差不齐，可能差距较大，基础差的学生在可能不能接受太多的内容；而且，就算能“吸收”到全部内容，未必就能全部“消化”。 本节课选取来自《张邱建算经》的百钱买百鸡问题作为本次教学的主题。这样既能提高学生学习的兴趣，又能使学生容易掌握知识，还可以培养学生的民族自豪感和通过建立数学模型和设计程序解决实际问题的习惯。 【学生情况分析】 1、学生在本节课前学习高中信息技术新课程的《算法与程序设计》模块已经有一段时间了，学生对算法和程序设计有了一定的认识，但是在面对实际问题时如何设计算法并且用程序实现算法来解决问题上，尤其是对于无法用解析法解决或者是用解析法解决比较困难的问题如何设计算法还是没有什么思路； 2、“百钱买百鸡”问题的数学模型是解不定方程，学生在初中的数学课上学过。本次课在原有知识的基础上，通过对实际问题的分析找到合适的数学模型，使学生基本理解和掌握穷举法解题的思路； 【教学目标】 1、知识与技能 （1）了解非解析法解题的基本思路； （2）理解和掌握穷举法解题的思路， 2、过程与方法 经历分析问题、建立数学模型、编写和调试程序，得到最终结果的过程，理解和掌握用穷举法解题的基本思路与过程； 3、情感态度与价值观 （1）通过主题任务的完成，激发民族自豪感和自身的成就感； （2）通过小组讨论与探究活动，提高团队合作能力，促进探究的热情； （3）通过结合学习生活的实际例子，进一步提高利用信息技术解决学习、生活问题的能力。【教学重点与难点】 重点：用穷举法解题的基本思路和过程 难点：分析问题建立数学模型，构造算法 【教学策略】 教学理念与方法：以培养学生的信息素养为前提，遵循“学生是学习的主体，教师是学习的指导者”的新课程教学理念，根据本节课中各个知识点的联系，采用了“主题任务”的教学模式，通过任务驱动法，利用多媒体教学系统和投影设备，使学生在任务中学习，在实践中探究，在探究中总结归纳知识规律和方法，加强知识的实际应用。 问题概述 一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少）。 这是一个古典数学问题，设一百只鸡中公鸡、母鸡、小鸡分别为x，y，z，问题化为三元一次方程组： 这里x,y,z为正整数，且z是3的倍数；由于鸡和钱的总数都是100，可以确定x,y,z的取值范围： 1) x的取值范围为1～20 2) y的取值范围为1～33 3) z的取值范围为3～99，步长为3 对于这个问题我们可以用穷举的方法，遍历x,y,z的所有可能组合，最后得到问题的解。当然也可以简化算法去完成这个问题。 数据要求 问题中的常量：无 问题的输入：无 问题的输出：int x，y，z /*公鸡、母鸡、小鸡的只数*/ 三重循环做法（穷举法） #include 1.兔子繁衍问题： #include 2.素数判断及输出问题： #include 3.百钱百鸡问题（穷举法） #include C趣味编程百例(11)百钱百鸡问题 36.百钱百鸡问题 中国古代数学家张丘建在他的《算经》中提出了的"百钱买百鸡问题"：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ *题目分析与算法设计 设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程： 5x+3y+z/3=100 x+y+z=100 所以此问题可归结为求这个不定方程的整数解。 由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。 *程序说明与注释 #include void main() { int x,y,z,j=0; printf("Folleing are possible plans to buy 100 fowls with 100 Yuan.\n"); for(x=0;x<=20;x++) /*外层循环控制鸡翁数*/ for(y=0;y<=33;y++) /*内层循环控制鸡母数y在0~33变化*/ { z=100-x-y; /*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/ if(z%3==0&&5*x+3*y+z/3==100) /*验证取z值的合理性及得到一组解的合理性*/ printf("%2d:cock=%2d hen=%2d chicken=%2d\n",++j,x,y,z); } } *运行结果 Follwing are possible plans to buy 100 fowls with 100 Yuan. 1:cock=0 hen=25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=84 *总是的进一步讨论 这类求解不定方程总理的实现，各层循环的控制变量直接与方程未知数有关，且采用对未知数的取值范上穷举和组合的方法来复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数，提高程序的执行效率，请读者考虑。 百鸡问题——不定方程 中国古代数学名著《张邱建算经》中曾记载一道闻名世界的百鸡问题，题曰：“公鸡一只值钱5，母鸡一只值钱3，小鸡三只值钱1，今有钱一百，买鸡一百只，问公鸡、母鸡、小鸡各几何？”这是一道不定方程的问题，它可以在许多不定方程的书中找到，百鸡问题既很实际又很有趣，在其流传的一千多年中，人们为它的来源编织了好多美妙的传说，下面的故事就是其中的一例：公元前五世纪，有位姓张的贫苦人家的少年，他们全家只靠少年的父亲张老头卖鸡来维持生活。这位少年聪明好学，又特别喜爱数学，他在十二三岁时，就已攻读了《九章算术》等数学名著，当地人称他为“张神童”，“张神童”的名字传开后，引起了一些人的兴趣。一天，一位官员拿来一百文钱，要求按当时的鸡价：公鸡每只五文，母鸡每只三文，小鸡每三只一文，购买恰好一百只鸡。“张神童”为一愁莫展的父亲解决了难题，他给来人送上4只公鸡，18只母鸡和78只小鸡，共百鸡，值钱百文。第二天此人又带来一百文钱，还要买一百只鸡，但不能与上次重复。这次“张神童”让父亲拿出18只公鸡，11只母鸡和81只小鸡，显而易见鸡值百钱，满足了来人的要求。第三天，这个人带着一百文钱再次来到张家，还要求百钱买百鸡，且不能与上两次重复，“张神童”又一次为父亲解了围，他让父亲给来人12只公鸡，4只母鸡和84只小鸡，又凑成了百鸡值百钱，三次的考验使这位官员对“张神童”的神机妙算赞叹不已，从此“张神童”的名气更大了，这位“张神童”据说就是我国著名的数学家张邱建。 百鸡问题实际上是不定方程问题，用现在的解法比较容易。我们不妨设公鸡、母鸡、小鸡各为x、y、z，则根据题意得： 求此方程的正整数解。 将（2）×3-（1）得7x+4y=100……（3）由此得出x是4的倍数，且x＜14，于是x只能是4，8，12代入（3）可得y的三个对应解是8，11，4，所以此问题有三组正整数解： 百鸡百钱问题JAVA解 百钱买百鸡的问题算是一套非常经典的不定方程的问题，题目很简单：公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱， 用100文钱买一百只鸡,其中公鸡，母鸡，小鸡都必须要有，问公鸡，母鸡，小鸡要买多少只刚好凑足100文钱。 分析：估计现在小学生都能手工推算这套题，只不过我们用计算机来推算，我们可以设公鸡为x，母鸡为y，小鸡为z，那么我们 可以得出如下的不定方程， x+y+z=100, 5x+3y+z/3=100， 下面再看看x，y，z的取值范围。 由于只有100文钱，则5x<100 => 0 for(l=1;l<=33;l++){ n=100-m-l; if((n%3==0)&&(5*m+3*l+n/3==100)){ System.out.println("公鸡有："+m+"只，母鸡有："+l+"只，小鸡有："+n+"只。"); } } } } } 百钱买百鸡问题 Time Limit: 1 Sec Memory Limit: 2 MB Submit: 1120 Solved: 161 [Submit][Status][Web Board] Description “百钱买百鸡”是我国著名的古代数学问题,中国古代数学家张丘建在他的《算经》中提出了这样一个问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何? 你的任务是求解下面这个问题。问题是这样描述的:a文钱可买一只公鸡,b文钱可买一只母鸡,c文钱可买d只小鸡。用m文钱买n只鸡,那么有公鸡x只、母鸡y只、小鸡z只。求解出符合题意的x,y,z。 Input 输入为一张表。第一行是一个固定不变的表头,格式见sample。后面有多行,每行为一组测试数据。每组测试数据由6个整数组成,分别为“a,b,c/d,m,n”。满足0 Sample Input COCK,HEN,CHICK,MONEY,CHICKS 3,2,1/3,100,100 5,3,1/3,100,100 8,5,1/7,100,100 8,5,1/7,300,300 Sample Output COCKS,HENS,CHICKS 0,40,60 5,32,63 10,24,66 15,16,69 20,8,72 25,0,75 COCKS,HENS,CHICKS 0,25,75 4,18,78百钱买百鸡实验报告
C程序设计：百钱百鸡问题
百鸡百钱问题实验报告
利用“百钱买百鸡”探讨穷举法
百钱买百鸡的三种做法 C语言
百钱百鸡经典例题
C趣味编程百例(11)百钱百鸡问题
百鸡问题-不定方程
百鸡百钱问题
百钱买百鸡问题