1、算法设计与分析实验一学 号 *天津城建大学算法设计与分析实验报告一学生姓名张曾然专业、班级16软件二班指导教师唐国峰成绩计算机与信息工程学院软件工程系2018 年 9 月 19 日实验一：递归策略运用练习一、实验目的本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验一_学号_姓名”，如“算法
2、设计与分析实验一_09290101_张三”。 b 压缩包内为一个“算法设计与分析实验一_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2018年10月10日16:00。三、实验项目1运用递归策略设计算法实现下述题目的求解过程。题目列表如下：【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七
3、分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；
4、第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少
5、桃子？（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不
6、会传染人，第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 是另一个可能的答案。 请你利用计算机的优势，帮助警察叔叔快速找到所有答
7、案。 每个答案占一行。形如：12+34+56+7-8+9123+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位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。四、实验过程（一）题目一：运动会开了N天，一共发出金牌M枚。第一
8、天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。1.题目分析由题意得，本题存在两个未知数，分别是金牌的总数m和运动会进行的天数n，所以很难从第一天开始进行正向推倒从而算出本题的答案，经过思考我发现本题的突破口是在“到了第N天刚好还有金牌N枚”这句话上，所以可以从最后一天发的金牌数中开始切入。推倒出了表达式就可以采用递归的思想来进行问题的解答了递归有两个重要组成部分：递归方程：前一天所剩金牌=当天所剩金牌*7/6+当天天数。边界条件：当天的前一天所剩金牌数和当天
9、的天数相等。2.算法构造在此论证算法设计中的一些必要的设计依据。已经完成了题目分析下面就要将递归方程：（前一天所剩金牌-当天天数）*6/7=当天所剩金牌用代码表示出来，可以通过一个二元数组或者链表结构将当前天数和剩余的金牌数存放起来，设置一个哨兵用来判断（前一天剩余的金牌数-当天天数）能否被7整除,若果不能被7整除则证明所设置的初值不正确，3.算法实现程序源代码（请写入必要的注释）。First类：package ;public class First public static int broken(int num, int today) /num为前一天所剩的金牌数，today为当天天数 i
10、f (num-today)%7!=0) /判断前一天所剩金牌数-当天天数能否被7整除，不可以返回0 return 0; else /如果可以返回当天剩余金牌的数量 return (num-today) *6/7; 测试类：package ;import java.util.LinkedList;public class Test static First one=new First(); public static void main(String args) LinkedList lt = new LinkedList(); for(int n=3;n=3,将n的初值设为3可以降低递归算法的
11、重复率 for(int m =1;m100;m+) /利用穷举法计算m的值 lt.add(0,m);/ 第一天没发之前一共有m枚金牌 for(int i=1;i=1;i-) /从最后一个王子开始往前算每一位王子所拥有的财产能否被9整除 /不能则跳出循环，n再加9，可以的话再判断前一位 if(princei+1%9!=0) break; else princei=princei+1*10/9+i; if(i=0) break; /当所有王子所拥有的财产都能被9整除，及经过若干次i-之后i变成了零 /跳出外循环，完成循环终止条件，得出结果 System.out.println(国王一共有+n+个儿
12、子); System.out.println(一共有资产+n*prince1+,总共分了+prince1+份); 4.运行结果5.经验归纳本题与第一题相似只是细微的部分发生了改变，设计的难点还是很难找到循环终止条件（三）题目三出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？1.题目分析由题意得，本题中仅存在一个未知数，一开始有多少条金鱼，由于已经给出了最后一天
13、卖出了11条金鱼这个信息所以，从后往前便能推出每一天卖之前有多少条金鱼：如上图所示第三天卖之前还有29条金鱼，经过归纳可得递推公式：f(n)=f(n-1)-f(n-1)/n+1/n f(n-1)=n/(1-n)*f(n)+1/n f(n)=(n+1/n*f(n+1)+1/(n+1)f(n)表示前一次有多少条鱼f(n+1)表示后一次有多少条鱼;边界条件：当函数中初值取值为5的时候，将11往前传递2.算法构造在此论证算法设计中的一些必要的设计依据。本题是最显而易见的循环算法，将第几次卖鱼看做一个函数给定一个初值，没有返回值的时候就根据递推方程继续调用自身，直至初值为5将数据传递归还3.算法实现程序
14、源代码（请写入必要的注释）。package ;public class Fish public static float fish(float n) /第几次卖鱼时共有多少条鱼 if(n=5) return (11); /如果是第五次卖鱼，则有11条鱼 else return (n+1)/n)*(fish(n+1)+1/(n+1); /前一次卖的鱼等于(n+1)/n)乘以后一次卖的鱼加上后一次分之一 public static void main(String args) float n; n=fish(1); /第1次卖鱼时共有多少条鱼 System.out.println(第一次共有+n+
15、条鱼); 4.运行结果5.经验归纳本题运用了最基本的递归算法思路，自身调用自身，达成条件后将数据传递归还，加深了我对递归含义的运用，以及对该类算法的理解。（四）题目四：某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？。1.题目分析本题与第三题类似，由题意得：边界条件：到达八号站台，并将6作为返还值2.算法构造在此论证算法设计中的一些必要的设计依据。本题是最显而易见的循环算法，将第几
16、站上车看做一个函数并给定传入的参数，没有返回值的时候就根据递推方程继续调用自身，直至传入参数为6时将数据传递归还因为到达第一站时是没有上下车人员的变化的所以从第二站开始算起，递归方程随之改变：station(n)=2*(station(n+1)+n-7);3.算法实现程序源代码（请写入必要的注释）。package ;package ;public class Bus public static float station(float n) /第几站上车时车上有多少人 /第一站上车时人员不发生变动，所以将第二站作为始发点 if(n7) return (2*(station(n+1)+n-7);
17、/如果传入值不是最后一站则向后递归寻找边界值 else return (6); public static void main(String args) float n; n=station(1); /第1站公交车上有多少人 System.out.println(第一站公交车上有+n+人); 4.运行结果5.经验归纳本题运用了最基本的递归算法思路，自身调用自身，达成条件后将数据传递归还，加深了我对递归含义的运用，以及对该类算法的理解。（五）题目五：猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？。
18、1.题目分析：由题意得，本题只存在一个未知数摘来桃子的数量（与有多少只猴子是无关的），分析后得出第九天刚好吃完，而第九天也吃了剩下的二分之一加1，所以第九天吃之前剩了2个桃子，第八天吃完剩了两个，如下表可得递归方程：递归方程：E(N)=(E(N+1)+1)*2 边界条件：N等于9时，返还值为22.算法构造在此论证算法设计中的一些必要的设计依据。本题是最显而易见的循环算法，将第几天吃之前还剩多少看做一个函数并给定传入的参数，没有返回值的时候就根据递推方程继续调用自身，直至传入参数为9时将数据传递归还3.算法实现程序源代码（请写入必要的注释）。package ;public class Monke
19、y public static float eatPeach(float n) if(n=9) return (2); /循环终止条件,第九天吃之前剩了两个桃子 else return (2*(eatPeach(n+1)+1);/如果不满足条件，当天吃之前剩的=（后一天的）+1）*2 public static void main(String args) float n; n=eatPeach(1); /算第几天猴子吃之前有多少个桃子eatPeach方法体中写天数 System.out.println(猴子们摘来了+n+个桃子); 4.运行结果5.经验归纳本题运用了最基本的递归算法思路，自身
20、调用自身，达成条件后将数据传递归还，加深了我对递归含义的运用，以及对该类算法的理解。（六）题目六：小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？。1.题目分析由题意得，第六天刚好读完最后三页，所以如下表可得递归方程：边界条件：N等于6时，返还值是32.算法构造在此论证算法设计中的一些必要的设计依据。在此论证算法设计中的一些必要的设计依据。本题是最显而易见的循环算法，将第几天读之前还剩多少页没读看做一个函数并给定传入的参数，没有返回值的时候就根据递推方程继续调用自身，直至传入参数为6时将数据传递归还3.算法实现程序源代码
21、（请写入必要的注释）。package ;public class Reading public static float Read(float n) if(n=6) return (3); /循环终止条件,第六天读之前有3页没读 else return (2*(Read(n+1)+2);/如果不满足条件，当天读之前剩的页数=（后一天的）+2）*2 public static void main(String args) float n; n=Read(1); /算第1天读之前有多少页没读等价于求全书有多少页 System.out.println(整本书有+n+页); 4.运行结果5.经验归纳本
22、题基于最基本的递归算法思路，自身调用自身，达成条件后将数据传递归还，加深了我对递归含义的运用，以及对该类算法的理解。（七）题目七：日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？1.题目分析：由题意得，最后大家手中的桔子都一样多，每个人最后都有252
23、0/6=420个桔子，本题与之前的题目不太一样差异在于递归终点与递归起点之间存在联系，可以推出边界条件：第一个孩子得到的桔子总数等于平均数-最后一个孩子分给老大的差乘以8/7.2.算法构造为了完成这道题目，我构建了一个二维数组ai0表示第i个孩子分出的桔子，ai1表示第i个孩子分到的桔子，定义了两个静态值：分母的最大值8，和分母的最小值3，算法实现如下：3.算法实现程序源代码（请写入必要的注释）。package ;public class Orange static int MAX=8;/分母最大值 static int MIN=3;/分母最小值 /ai0表示第i个孩子分出的桔子 /ai1表示
24、第i个孩子分到的桔子 public static int orange(int a,int i) int ave=2520/6; int p; if(i=0)/边界条件 /第一个孩子得到的桔子总数等于平均数-最后一个孩子分给老大的差乘以8/7. ai1=(ave-ave/(MIN-1)*(MAX-i)/(MAX-1-i); /第一个孩子分给第二个孩子的橘子数量 ai0=ai1-(ave-ave/(MIN-1); else ai1=ave*(MAX-i)/(MAX-i-1)-orange(a,i-1);/第i个孩子分到的 ai0=ai1+orange(a,i-1)-ave; /第i个孩子分出的
25、p=ai0; return p; public static void main(String args) int o=0,0,0,0,0,0,0,0,0,0,0,0; orange(o,5);/给数组里的六个元素赋值 for(int i=0;i=5;i+) System.out.println(第+(i+1)+个儿子最初有+oi1+个桔子); 4.运行结果5.经验归纳本题与之前的题目不太一样差异在于递归终点与递归起点之间存在联系，所以在分析初期一直找不到入手点，因为之前的题目都存在着明确的循环终点，本题就像一条衔尾蛇一样首尾相连，经过了一段时间的分析才推出了关系，明白了这种类型的题目，其入手点在于最后一个单位和第一个单位之间的联系，将其作为边界条件即可推出结果。（八）题目八：一种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。1.题目分析由题意得，前五天不会发作也不会传染给别人，所以可以得出边界条件：当天数小于等于五时，只有一个患者。递归方程为：第N天患病人数等于前一天被传染和发作的加上当天又传染的的减去当天被治愈好的。2.算法构造我先定义了一个函数diseaseDay，传入一个int值i；传出的结果就是第i天有多少患者，构造如下：边界条件：当天数小于等于五时，只有一个患者。递
