网站如何备份,一句话宣传自己的产品,免费正版高清素材库,网站如何提升seo排名1.问题描述2.问题分析3.算法设计4.知识点补充5.确定程序框架6.确定公鸡、母鸡和小鸡数量7.完整的程序8.问题拓展
完整源代码项目地址#xff0c;关注博主私信’源代码’后可获取
1.问题描述
中国古代数学家张丘建在他的《算经》中提出了一个著名的“百钱百鸡问题”#xf…1.问题描述2.问题分析3.算法设计4.知识点补充5.确定程序框架6.确定公鸡、母鸡和小鸡数量7.完整的程序8.问题拓展
完整源代码项目地址关注博主私信’源代码’后可获取
1.问题描述
中国古代数学家张丘建在他的《算经》中提出了一个著名的“百钱百鸡问题”一只公鸡值五钱一只母鸡值三钱三只小鸡值一钱现在要用百钱买百鸡请问公鸡、母鸡、小鸡各多少只
2.问题分析
用百钱如果只买公鸡最多可以买20只但题目要求买100只由此可知所买公鸡的数量肯定在020之间。同理母鸡的数量在033之间。在此不妨把公鸡、母鸡和小鸡的数量分别设为cock、hen、chicken则cockhenchicken100因此百钱买百鸡问题就转化成解不定方程组的问题。 3.算法设计
对于不定方程组我们可以利用穷举循环的方法来解决也就是通过对未知数可变范围的穷举验证方程在什么情况下成立从而得到相应的解。因公鸡的取值范围是020可用循环语句“for cock in range(0,21);”实现。钱的数量是固定的要买的鸡的数量也是固定的所以母鸡数量是受到公鸡数量限制的。同理小鸡数量受到公鸡和母鸡数量的限制因此我们可以利用三层循环的嵌套来解决第一层循环控制公鸡的数量第二层控制母鸡的数量最内层控制小鸡的数量。
4.知识点补充
结构化程序设计包括三种基本结构顺序结构、选择结构分支结构和循环结构重复结构利用这三种基本结构可以解决很多复杂问题。
·顺序结构一种简单的程序设计按照程序中语句的顺序依次执行每条语句都能被执行且只执行一次。
·选择结构包括简单选择和多分支选择结构可根据条件判断应该选择哪一条分支来执行相应的语句序列。简单选择结构采用简单或一般的if语句即可解决对于复杂的选择结构可以使用嵌套的if…elif…else语句实现。
·循环结构可根据给定条件判断是否需要重复执行某一相同程序段。
下面介绍Python语言的循环结构。
1while循环
while循环语法格式如下
while 判断条件: 执行语句
其中判断条件可以是任何表达式所有非空、非零的值都为True当判断条件为False时循环结束执行语句可以是单条语句也可以是一个语句块。
2for循环
for循环语法格式如下
for iterating_var in sequence: statements(s)
其中sequence是任意序列如列表数组、字典或元组等也可以通过range()函数产生一个整数列表以完成计数循环iterating_var是序列中需要遍历的元素statements是待执行的语句块。
range()函数使用格式如下
range([start , ] stop[ , step])
其中start为可选参数表示起始数stop为终止数如果range()函数只有一个参数n则将产生一个0(n-1)的整数列表也就是循环n-1次step为可选参数表示循环步长不写时默认步长为1。
需要注意的是while循环结构首先对while条件进行判断当条件为True时执行条件语句块当执行完语句块时再次判断while条件是否为True若仍然为True则继续执行语句块直到条件为False时结束循环。
while循环结构的流程图如图所示。 3for循环结构
for循环结构首先对for语句的条件判断游标序列都会有一个游标游标一般从第0个位置开始指向序列的第0个位置也就是序列的第一个元素判断序列sequence中是否有元素。如果有就将这个元素赋值给iterating_var然后执行循环体语句块执行完成后游标下移一位再次判断该位置是否有元素如果有继续将该元素赋值给iterating_var继续执行循环语句块游标再往下移一位一直循环下去直到下一个位置没有元素时结束循环。
for循环结构的流程图如图所示。 在循环语句中循环体可以是由一个或多个语句构成的当其中某个语句是循环语句时即一个循环体中完整地包含了另外一个循环就形成了循环嵌套结构我们称之为多重循环并且把这个循环语句称为外层循环语句而把循环体中的循环语句称为内层循环语句。在理解多重循环语句时只要把内层循环语句看作是外层循环语句的循环体的一部分就可以了。在程序执行时外层循环语句与内层循环语句的关系有点像钟表的时针与分针的关系分针走了60格时针才走1格。对于多重循环来说只有内层循环语句执行到判断条件为假时才返回到其上层循环语句继续执行。
5确定程序框架
在设计循环时首先要考虑循环的三要素即循环变量的初值、循环的控制条件和使循环趋于结束的循环变量值的改变。
针对本题来说每层循环的初值是0即买的100只鸡中可能没有公鸡也可能没有母鸡或小鸡循环的控制条件是公鸡、母鸡和小鸡用百钱最多能够买到的数量根据上面分析可知公鸡最多20只母鸡最多33只小鸡最多100只虽然百钱最多可以买到300只小鸡但题目要求只买100只穷举循环的特点就是把所有情况都考虑到因此每层循环执行一次对应循环变量的值就要加1。
程序流程图如图所示。 # 根据流程图构建程序框架如下
cock 0
while cock 20:# 内层循环控制母鸡数量取值范围为033hen 0while hen 33:#内层循环控制小鸡数量取值范围为0100chicken 0while chicken 100:#条件控制print(cock%2d,hen%2d,chicken%2d\n %(cock,hen,chicken))chicken 1hen 1cock 16确定公鸡、母鸡和小鸡数量
根据这三层循环我们可以得到很多种方案在这些方案中有些是不符合cockhenchicken100并且5×cock3×henchicken/3100这两个条件的。因此结果输出之前我们要把合理的方案筛选出来即如果结果满足cockhenchicken100和5×cock3×henchicken/3100则输出。很明显控制条件即为语句if(5×cock3×henchicken/3.0100)and(cockhenchicken100)。
注意在Python语言中使用and关键字表示“逻辑与”使用or关键字表示“逻辑或”使用not关键字表示“逻辑非”。另外运算符“/”表示除x除以y结果为带小数点的浮点数而运算符“//”表示取整除返回商的整数部分。
7完整的程序
根据上面的分析编写程序如下
%%time
# 百钱百鸡问题
if __name____main__:# cock表示公鸡数量hen表示母鸡数量chicken表示小鸡数量总共100只# 外层循环控制公鸡数量取值范围为020cock 0while cock 20:# 内层循环控制母鸡数量取值范围为033hen 0while hen 33:#内层循环控制小鸡数量取值范围为0100chicken 0while chicken 100:# 条件控制if (5 * cock 3 * hen chicken / 3.0 100) and (cock henchicken 100):print(cock%2d,hen%2d,chicken%2d\n %(cock,hen,chicken))chicken 1hen 1cock 1cock 0,hen25,chicken75cock 4,hen18,chicken78cock 8,hen11,chicken81cock12,hen 4,chicken84CPU times: user 56.9 ms, sys: 2.29 ms, total: 59.2 ms
Wall time: 56.1 ms8问题拓展
以上算法需要穷举尝试21×34×10172 114次算法的效率显然太低了。对于这类求解不定方程的问题各层循环的控制变量直接与方程的未知数相关并且采用对未知数的取值范围穷举和组合的方法得到全部的解。对于本题来说公鸡的数量确定后小鸡的数量就固定为100-cock-hen无须再进行穷举了此时约束条件只有一个即5×cock3×henchicken/3100这样我们利用两重循环即可求解本题代码如下
%%time
# 百钱百鸡问题if __name____main__:# 外层循环控制公鸡数量取整范围为020cock 0while cock 20:# 内层循环控制母鸡数量取值范围为030hen 0while hen 33:# 小鸡的数量chicken 100 - cock - henif 5 * cock 3 * hen chicken / 3.0 100:print(cock%2d,hen%2d,chicken%2d\n %(cock, hen, chicken))hen1cock1
cock 0,hen25,chicken75cock 4,hen18,chicken78cock 8,hen11,chicken81cock12,hen 4,chicken84CPU times: user 585 µs, sys: 0 ns, total: 585 µs
Wall time: 590 µs此算法只需穷举21×34714次实现时约束条件又限定chicken能被3整除时才会判断“5×cock3×henchicken/3.0100”这样便省去了chicken不能整除3时的算术计算和条件判断进一步提高了算法的效率。算法运行时间大幅缩短
