内容发布更新时间 : 2024/12/26 10:14:45星期一 下面是文章的全部内容请认真阅读。
学 号 1607070212
《算法设计与分析》
实验报告一
学专指成
生业导、
姓班教
名 级 师 绩
张曾然 16软件二班 唐国峰
计算机与信息工程学院软件工程系
2018 年 9 月 19 日
实验一：递归策略运用练习
一、实验目的
本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。
二、实验步骤与要求
1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容；
3．实验结束后，用统一的实验报告模板编写实验报告。
4．提交说明：
（1）电子版提交说明：
a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。
b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹，
其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。
（2）打印版提交说明：
a 不可随意更改模板样式。
b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号
字。
c 行间距：单倍行距。
（3）提交截止时间：2018年10月10日16:00。
三、 实验项目
1．运用递归策略设计算法实现下述题目的求解过程。
题目列表如下：
【必做题】
（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。
（2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；??；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？
（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个??，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？
（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？
（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此??，第六天读完了最后的三页，问全书有多少钱页？
（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。
【选做题】（5选3）
（1）为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！某批警察叔叔正在进行智力训练： 1 2 3 4 5 6 7 8 9 = 110;
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。
请你利用计算机的优势，帮助警察叔叔快速找到所有答案。 每个答案占一行。形如：
12+34+56+7-8+9 123+4+5+67-89
（2）递归将一个整数输出。形如654321，输出1,2,3,4,5,6 （3）用递归实现分解质因数。形如：12=2*2*3
（4）50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？
（5）电话号码对应的字符组合。题目：在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组