编程训练: 大学计算机 实验3 算法分析设计与应用
第1关：百钱买百鸡1
任务描述
本关任务：我国古代数学家张丘建在《算经》一书中提出的数学问题：
鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。
百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
相关知识
为了完成本关任务，你需要掌握：1.穷举法思想，2.如何用循环实现穷举法。
程序设计思路
定义变量i,j,k分别代表公鸡、母鸡、小鸡数量，定义变量n代表总的方案数量。
之后，设置三重循环，逐一测试是否满足条件，满足条件，则变量n加1。
参考代码如下：
n=0foriinrange(21):forjinrange(34):forkinrange(0,101,3):ifi+j+k==100and i*5+j*3+k//3==100:n=n+1 print(f"第{n}种方法：公鸡{i}只，母鸡{j}只，小鸡{k}只")print(f"百钱买百鸡共有{n}种方法")测试答案:
#请在下方编写代码##############begin###############n=0foriinrange(21):# 公鸡最多20只（5*20=100）forjinrange(34):# 母鸡最多33只（3*33=99）forkinrange(0,101,3):# 小鸡数量必须是3的倍数ifi + j + k==100and i *5+ j *3+ k //3==100: n=n +1print(f"第{n}种方法：公鸡{i}只，母鸡{j}只，小鸡{k}只")print(f"百钱买百鸡共有{n}种方法")#############end##################第2关：百钱买百鸡2
任务描述
本关任务：
设公鸡每只5元，母鸡每只3元，小鸡每元3只，现用x元钱买y只鸡。
编写一个程序，输入x和y，算出各买多少只鸡？(公鸡、母鸡、小鸡必须都有）如果有多个符合条件的结果，则都显示出来。如果没有符合条件的结果，则显示"无解"
若输入:
钱：100
鸡：100
结果如下所示
**公鸡4只母鸡18只小鸡78只 公鸡8只母鸡11只小鸡81只 公鸡12只母鸡4只小鸡84只**测试答案:
x=eval(input("钱："))y=eval(input("鸡："))c=0# 方案数计数器# 公鸡、母鸡、小鸡都必须有，所以从1开始foriinrange(1, y +1):# 公鸡数量forjinrange(1, y +1):# 母鸡数量forkinrange(3, y +1,3):# 小鸡数量必须是3的倍数ifi + j + k==y and5* i +3* j + k //3==x: print(f"公鸡{i}只母鸡{j}只小鸡{k}只")c+=1ifc==0: print("无解")第3关：鸡兔同笼问题
任务描述
任务说明：大约在1500年前，《孙子算经》中就记载了这个有趣的问题：
“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”
意思是，有若干只鸡和兔子关在同一个笼子里，从上面数有35个头，从下面数有94只脚，
问：笼子中有多少只鸡？多少只兔子？
范例程序：
假设i,j代表鸡和兔的数量，n代表总的方案数量
n=0foriinrange(36):forjinrange(36):ifi+j==35and i*2+j*4==94:n=n+1 print(f"第{n}种方法：鸡{i}只，兔{j}只")print(f"鸡兔同笼共有{n}种方法")测试答案:
t=eval(input())# 头的个数j=eval(input())# 脚的个数n=0# 方案数计数器foriinrange(t +1):# 鸡的数量forkinrange(t +1):# 兔的数量ifi + k==t and2* i +4* k==j: n+=1print(f"鸡{i}只兔子{k}只")ifn==0: print("无解")第4关：二分法猜数
任务描述
本关任务：假如有一个游戏是让你在1-100之间猜一个数:
如果猜对了，那么显示你猜对了；
否则继续猜，并提示猜大了还是猜小了，直到猜对为止；
最后显示猜的总次数。
相关知识
为了完成本关任务，你需要掌握：1.掌握二分法的概念，2.熟练使用循环语句。
编程提示
用二分法猜数，最多猜的次数为 log2n
以下为随机猜数的游戏，被猜的数字和第一次猜的数都随机生成，运行程序，观察程序运行结果。
importrandom target=random.randint(1,100)# 随机生成一个1-100之内的整数作为要被猜的数字guess=random.randint(1,100)#随机生成第一次猜的数字print(f"target= {target}")max1=100# 赋最大值初始值min1=0# 赋最小值初始值count=1# 赋猜测次数初始值为1次whileTrue:# 没猜中就不停循环ifguess<target: print(f"第{count}次，{guess}<{target}")min1=guess# 猜测数字小了，将此次猜测结果赋给min1,作为下次最小值guess=(guess + max1)//2 count+=1elifguess>target: print(f"第{count}次，{guess}> {target}")max1=guess# 猜测数字大了，将此次猜测结果赋给max1,作为下次最大值guess=(min1 + guess)//2 count+=1else:# 猜中了就退出print(f"第{count}次，{guess}= {target}！")breakprint(f"猜的总次数为：{count}")测试答案:
target=eval(input("请输入要猜的数（1-100）:"))guess=eval(input("请输入第一次猜的数（1-100）:"))# 请在下方编写代码##############begin###############max1=100# 赋最大值初始值min1=0# 赋最小值初始值count=1# 赋猜测次数初始值为1次whileTrue:# 没猜中就不停循环ifguess<target: print(f"第{count}次，{guess}<{target}")min1=guess# 猜测数字小了，将此次猜测结果赋给min1,作为下次最小值guess=(guess + max1)//2count+=1elifguess>target: print(f"第{count}次，{guess}> {target}")max1=guess# 猜测数字大了，将此次猜测结果赋给max1,作为下次最大值guess=(min1 + guess)//2count+=1else:# 猜中了就退出print(f"第{count}次，{guess}= {target}！")breakprint(f"猜的总次数为：{count}")#############end##################第5关：求n的阶乘
任务描述
本关任务：输入非负整数n，求n的阶乘，如果输入的 n为负数，则显示“输入有误”。
为了完成本关任务，你需要掌握：（1）Python的函数定义及调用；（2）递归的思想。
编程分析
阶乘是一个典型的递归算法,假设所求的阶乘用函数fac(n)表示：
（1）当 n=0 或 n=1时 ,fac(n)=1
（2）当 n>1时，fac(n)=n*fac(n-1)
测试说明
系统对你编写的代码进行测试：
样例输入：请输入n：6
样例输出：6的阶乘为：720
样例输入：请输入n：-10
样例输出：输入有误
开始你的任务吧，祝你成功！
测试答案:
#请在下方编写代码##############begin################ 定义阶乘函数def fac(n):ifn==0or n==1:return1else:returnn * fac(n -1)# 输入nn=eval(input("请输入n："))# 判断输入是否合法ifn<0: print("输入有误")else: result=fac(n)print(f"{n}的阶乘为：{result}")#############end##################第6关：斐波那契数列
任务描述
本关任务：编写一个能计算斐波那契数列中第x个数的小程序。
相关知识
为了完成本关任务，你需要掌握：1.什么是斐波那契数列，2.for循环、函数的递归
什么是斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
有一对兔子，从出生后第 3 个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，每个月的兔子数形成的数为斐波那契额数列
在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
测试答案:
# 定义斐波那契函数（递归方式）def fib(n):ifn==1or n==2:return1else:returnfib(n -1)+ fib(n -2)# 输入nn=eval(input("请输入n："))# 判断输入是否合法ifn<=0: print("输入有误")else: result=fib(n)print(f"第{n}的数为：{result}")