《算法设计与分析报告》趣味题.docx

学号 10770114
《算法设计与分析》
实验报告一
学 生 姓 名 王哲
专业、 班级 10软件1班
指 导 教 师 唐国峰
成 绩
电子与信息工程系
2012年10月10日
实验一：递归策略运用练****br/>、实验目的
本次实验是针对递归算法的算法设计及应用练****旨在加深学生对该算法原理的理解， 提高
学生运用该算法解决问题的能力。
、实验步骤与要求
1实验前复****课程所学知识以及阅读和理解指定的课外阅读材料；
学生独自完成实验指定内容；
3 •实验结束后，用统一的实验报告模板编写实验报告 。
提交说明：
电子版提交说明：
a需要提交 Winrar压缩包，文件名为“《算法设计与分析》实验一 一学号_姓名”， 如“《算法设计与分析》实验一 _09290101_张三”。
b压缩包内为一个“《算法设计与分析》实验一 一学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序” ，另一个文件夹命名为“实验
报告电子版”。其下分别放置对应实验成果物。
打印版提交说明：
a不可随意更改模板样式。
b字体：中文为宋体，大小为 10号字，英文为 Time New Roman，大小为10号 字。
c行间距：单倍行距。
提交截止时间： 2012年10月31日16:00。
三、实验项目
1 •运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：
运动会开了 N天，一共发岀金牌 M枚。第一天发金牌 1枚加剩下的七分之一枚，第
二天发金牌2枚加剩下的七分之一枚， 第3天发金牌3枚加剩下的七分之一枚， 以后每天都照此
办理。到了第 N天刚好还有金牌 N枚，到此金牌全部发完。编程求 N和M。
国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿
子一份，再加上剩余财产的 1/10 ;给第二个儿子两份，再加上剩余财产的 1/10 ;……；给第i
个儿子i份，再加上剩余财产的 1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国
王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼
的三分之一加三分之一条金鱼； 第三次卖岀剩余金鱼的四分之一加四分之一条金鱼； 第四次卖岀
剩余金鱼的五分之一加五分之一条金鱼；现在还剩下 11条金鱼，在出售金鱼时不能把金鱼切开
或者有任何破损的。问这鱼缸里原有多少条金鱼？
某路公共汽车，总共有八站，从一号站发轩时车上已有 n位乘客，到了第二站先下一
半乘客，再上来了六位乘客；到了第三站也先下一半乘客， 再上来了五位乘客， 以后每到一站都
先下车上已有的一半乘客，再上来了乘客比前一站少一个 ，到了终点站车上还有乘客六人，
问发车时车上的乘客有多少？
猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只(即第二天
吃剩下的一半加一只，以此类推) ，第九天正好吃完，问猴子们摘来了多少桃子？
小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天 如此……，第六天读完了最后的三页，问全书有多少钱页？
日本著名数学游戏专家中村义作教授提岀这样一个问题： 父亲将2520个桔子分给六个
儿子。分完 后父亲说：“老大将分给你的桔子的 1/8给老二；老二拿到后连同原先的桔子分 1/7
给老三；老三拿到后连同原先的桔子分 1/6给老四；老四拿到后连同原先的桔子分 1/5给老五；
老五拿到后连同原先的桔子分 1/4给老六；老六拿到后连同原先的桔子分 1/3给老大”。结果大
家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
四、实验过程
题目一：运动会开了 N天，一共发岀金牌 M枚。第一天发金牌 1枚加剩下的七分之一枚, 第二天发金牌 2枚加剩下的七分之一枚，第 3天发金牌3枚加剩下的七分之一枚，以后每
天都照此办理。到了第 N天刚好还有金牌 N枚，到此金牌全部发完。编程求 N和M。
1.
题目分析
分析此题，可以按照从第一天开始递归，每次和前一天的金牌剩余数的关系为： (前一
天金牌剩余数-当天为第几天)*6/7-当天金牌剩余数，递归终点为：当某一天的前一天的 金牌剩余数等于当天的天数，即为终止点。
2.
算法构造
通过双重循环来寻找天数和金牌数，构造一个存放每天剩余金牌数的容器，我使用的是
java语言，选择了 LinkedList, 在构造递归关系时候，主要要判断 该天金牌数-天数
之差是否能是7的倍数，如果不能，则设置为0，在后面的条件判断时候予以舍弃情况。
3.
import
算法实现