《算法设计与分析》实验一_实验报告电子版.doc

学 号 09710118算法设计与分析实验报告一学生姓名范振山专业、班级09计算机一班指导教师唐国峰成绩电子与信息工程系2012 年 3 月 9 日实验一：递归策略运用练习一、实验目的本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2学生独自完成实验指定内容；3实验结束后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验一_学号_姓名”，如“算法设计与分析实验一_09290101_张三”。 b 压缩包内为一个“算法设计与分析实验一_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c 行间距：单倍行距。（3）提交截止时间：2012年3月23日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给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？四、实验过程（一）题目一：运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。1. 题目分析第一天有(M-1)*1/7枚金牌，第二天又金牌2+f(2)-2*1/7,依次类推，第n天就有f(n,2)=f(n,1)-(1+(f(n,1)-1)/7)枚金牌。2. 算法构造在此论证算法设计中的一些必要的设计依据。第一天的金牌数量为f(n,1)，发金牌的数量为1+(f(n,1)-1)/7,，第二天的金牌数量为f(n,2),发的金牌数量为2+(f(n,2)-2)/7，则f(n,2)=f(n,1)-(1+(f(n,1)-1)/7)，类推得：f(n,i)=f(n,i+1)+i+(f(n,i)-i)/7;3. 算法实现程序源代码（请写入必要的注释）。/ 预编译命令#include using namespace std;/定义每一天发放奖牌中从剩余部分来源的几分之一。如此处为7即为1/7#define Fenmu 7/递归函数，nMedalSum为第N天奖牌的总数，包括当天分发的和剩余的两部分之和int nMedalSum(int i,int n)int result=0;if (i = n) result=Fenmu-1;elseresult=(nMedalSum(i+1,n)*Fenmu/(Fenmu-1)+i);return result; /主函数void main() int n=Fenmu-1;/运动会连续持续天数int m;/奖牌总数for (int i=1; i=n; i+)/当天的奖牌总数必须被分母减一整除，以合乎题意，作为头天剩余奖牌数if ( nMedalSum(i,n)%(Fenmu-1)=0)if(n=i)break;else/一旦发现有余数，则当前天数不合法，天数需加分母减一n=n+Fenmu-1; cout 运动会连续召开 n 天 ,共有金牌 nMedalSum(1,n) 块。 endl endl;cout 具体分发情况如下所示： endl endl;for(i=1;i=n;i+)cout 第 i 天发奖牌数为 i + (nMedalSum(i,n)-i)/7 块，剩余 (nMedalSum(i,n)-i)/7*6 块 endl;cout endl;system(pause);4 运行结果5 经验归纳这道程序题的基本思想已理解，可是程序中的应用却不是那么好。因为看老师的例子之后觉得更难理解。不过所幸的是在同学的讲解下把那部分公式理解了。可是叫我再写的话这很复杂，我就不一定写的出来了。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？1.题目分析有n个儿子就有n分财产，并且由题意可知2.算法构造在此论证算法设计中的一些必要的设计依据。国王有n个儿子，那么第总共有N份财产，那么n个儿子得到的是n份加上剩余的1/10,第n个儿子得到的是n份。，没有剩余3.算法实现第一个儿子得到的是1+（N-1）1/10,第二个儿子得到的是2+N(2)*1/10,剩下的是f(3)=9/10*(f2-2)所以第i个儿子是fi-1=10/9*fi+(i-1)4. 算法实现程序源代码（请写入必要的注释）。#includeusing namespace std;#includeusing namespace std;/主函数int main()int i; int n=0;n=n+9;int f100;fn=n;for(i=n;i1;i-)fi+1=10/9*(fi+i);cout老国王共有:n儿子endl;cout财产共分了n+nendl;return 0;运行结果4,经验归纳在做这个实验的时候，我再推推公式上的推倒花了很多时间，因为对题目的理解不是很透彻，所以在计算的时候就老是出错。但是因为编程的基础不行所以实在是不能把每一次的财产算出。（三）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？（一）题目一：（基于冒泡排序）1 题目分析总共有金鱼f(1)条，所以第一次卖出f(1)*1/2+1/2,第一次卖出之前剩余的金鱼数位f(1);第2次卖出的为1/3f(0)+1/3,第2此卖出去之前的金鱼数：f(2)=1/2f(1)-1/2;第三次卖出的金鱼数为：1/4f(3)+1/4;第三次卖出之前的金鱼数为：f(3)=2/3*f(2)-1/3;直到第五次卖出去之前的金鱼数为f(5)=4/5f(4)-1/5.2 算法构造在此论证算法设计中的一些必要的设计依据。因此推出i/(i-1)f(n)-1/2=f(i-1)3 算法实现程序源代码（请写入必要的注释）。/*/* GOLDFISH SELLING PROBLEM */* 陈静雯 2012年3月20日 */*/ / 预编译命令#include using namespace std; /最后剩余的金鱼数量#define SPARE_FISH_NUM 11/总共出售金鱼的次数#define SALES_TIMES 4 /递归函数，nGoldfishNum为求第N次销售金鱼前的总金鱼数的方法int nGoldfishNum(int i,int aSALES_TIMES) int result=0; if (i+1 = SALES_TIMES) /i+1表示出售次数 ai=(int)(SPARE_FISH_NUM+(1/(double)(i+2)*(i+2)/(i+1)+0.5); result=ai; else ai=(int)(nGoldfishNum(i+1,a)+(1/(double)(i+2)*(i+2)/(i+1)+0.5); result=ai; return result; /主函数void main() int GoldfishNumSALES_TIMES; /赋初始值 for(int i=0;iSALES_TIMES;i+) GoldfishNumi=0; int m=nGoldfishNum(0,GoldfishNum); /输出结果 cout /*/ endl; cout /* GOLDFISH SELLING PROBLEM */ endl; cout /* 陈静雯 2012年3月20日 */ endl; cout /*/ endl endl; cout 共有金鱼 GoldfishNum0 条，详细销售情况如下所示： endl endl; /格式化输出信息内容 for(i=0;i+1=SALES_TIMES;i+) if(i+1=SALES_TIMES) cout 第 i+1 次出售金鱼 GoldfishNumi-SPARE_FISH_NUM 条，; cout 剩余 SPARE_FISH_NUM 条。; else cout 第 i+1 次出售金鱼 GoldfishNumi-GoldfishNumi+1 条，; cout 剩余 GoldfishNumi+1 条；; cout endl; cout endl; system(pause); 4 运行结果5. 经验归纳每次做这类题的时候，第一步就遇见了很大的困难，就是在计算递推公式时不能翻译成老师的那种形式。因为原程序改编之后没有错误但是不能出结果。所以我就把形式改成别的了。（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（一）题目一：（基于冒泡排序）1 题目分析设下一站下车之前的初始人数为f(1),第二站下车的人数人数为f(1)/2-6,第二站下之前的人数为f(2)=f(1);第三站下车之前的人数为f(3)=f(2)/2-5,下车之前的人数为f(3)=f(2)/2-6第四站下车之前的人数为f(4)=1/2f(3)-4,下车之前的人数为f(4)=1/2f(3)-4;第五站下车之前的人数为f(4)1/2-3,下车之前的人数为f(5)=1/2f(5)-22 算法构造在此论证算法设计中的一些必要的设计依据。因此推出f(i)=1/2*f(i-1)-(8-i)3 算法实现程序源代码（请写入必要的注释）。#includeusing namespace std;/递归函数getoutsum为第n站下车之后的人数int getoutsum(int i,int n)int result=0;if(i=7)result=6;elseresult=(getoutsum(i+1,n)-7+i)*2;return result;/主函数void main() int i; int n=7;/总站数 for(i=1;i=7;i+)if(getoutsum(i,n)%7=0)if(n=i)break;elsen=7+n;cout发车时车上的乘客:getoutsum(1,n)endl;4 运行结果5 经验归纳这次的实验虽然用自己的方法改编了，可是运行的没错误但是结果不显示。（五）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（一）题目一：（基于冒泡排序）1 题目分析第九天吃了一半还加一个，所以还剩两个。2 算法构造在此论证算法设计中的一些必要的设计依据。f(i)=(f(i+1)+1)*2为递推公式；3 算法实现程序源代码（请写入必要的注释）。#includeusing namespace std;/递归函数eatsum为第九天之前吃的桃子数量int eatsum(int i,int n)int result=0;if(i=n)result=2;/第九天吃之前还剩余的数量else result=(eatsum(i+1,n)+1)*2;/递归公式return result;/主函数void main()int i;int n=9;/总天数for(i=1;i=9;i+)if(eatsum(i,n)%9=0)if(n=i)break;elsen=9+n;4.试验结果4 经验归纳我写出的这个程序是由发金牌的程序改编的，能容易理解。不过我本来是想用卖金鱼的程序理解后再写的，可是卖金鱼的递推公式很难理解，for循环还是两个部分，所以我就选择了更易懂的的来写了。（六）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？（一）题目一：（基于冒泡排序）1 题目分析第六天剩余三页，所以就用每天读的和第二天读的之和为总页数2 算法构造在此论证算法设计中的一些必要的设计依据。F(i)=(f(i+1)+2)*2为递推公式；3 算法实现程序源代码（请写入必要的注释）。#includeusing namespace std;/递归函数readsum为第九天读之前的页数int readsum(int i,int n)int result=0;if(i=n)result=3;elseresult=(readsum(i+1,n)+2)*2;return result;/主函数void main()int i;int n=6;/总天数for(i=1;i=6;i+)if(readsum(i,n)%6=0)if(n=i)break;elsen=6+n;cout总共的页数:readsum(1,n)endl;4 运行结果5 经验归纳首先要理解调用函数如何用，再写个循环就行了，最后就是输出结果。（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？（一）题目一：（基于冒泡排序）6 题目分析每个儿子有之前分到的和后面得到的橘子，大儿子先给后得，其他儿子先得后给，但是结果是一样的。7 算法构造在此论证算法设计中的一些必要的设计依据。8 算法实现程序源代码（请写入必要的注释）。/ 预编译命令#include using namespace std;#define ORANGE_NUMBER 2520/桔子总数#define SUN_NUMBER 6/孩子总数#define DENOMINATOR_MAX 8/均分分母最大值#define DENOMINATOR_MIN 3/均分分母最小值/递归函数，用来计算每个孩子分给弟弟的桔子数量/关于数组a62的解释：/ai0表示第i个孩子分出的桔子总数/ai1表示第i个孩子从国王那里分到的桔子总数int DistributeOrangeForBrother(int a62,int i)int average=ORANGE_NUMBER/SUN_NUMBER;int p;if (i=0)/第一个孩子从国王那里分到的桔子总数应为平均数减去最后一个孩子分出去的部分后乘以8/7。ai1 = (average-average/(DENOMINATOR_MIN-1)*(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i);/第一个孩子分给第二个孩子的桔子数量。 ai0 = ai1 - (average-average/(DENOMINATOR_MIN-1); else /第i个孩子从国王那里分到的桔子总数。 ai1 = average *(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i) - DistributeOrang