算法设计与分析实验一_14210501.doc

《算法设计与分析实验一_14210501.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验一_14210501.doc（16页珍藏版）》请在课桌文档上搜索。

1、 实验一：递归策略运用练习一、实验目的本次实验是针对递归算法的算法设计与应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1实验前复习课程所学知识以与阅读和理解指定的课外阅读材料；2学生独自完成实验指定容；3实验完毕后，用统一的实验报告模板编写实验报告。4提交说明： （1）电子版提交说明：a 需要提交Winrar压缩包，文件名为“算法设计与分析实验一_学号_”，如“算法设计与分析实验一_09290101_三”。b 压缩包为一个“算法设计与分析实验一_学号_”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电

2、子版”。其下分别放置对应实验成果物。 （2）打印版提交说明：a 不可随意更改模板样式。b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号字。 c行间距：单倍行距。（3）提交截止时间：2017年3月28日16:00。三、 实验项目1运用递归策略设计算法实现下述题目的求解过程。题目列表如下：必做题 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们

3、分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？（4）某路公共汽车

4、，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将252

5、0个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。选做题（5选3） （1）为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常

6、性地进行体力训练和智力训练！某批警察叔叔正在进行智力训练： 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+9123+4+5+67-89（2）递归将一个整数输出。形如654321，输出1,2,3,4,5,6（3）用递归实现分解质因数。形如：12=2*2*3（4

7、）50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？（5）对应的字符组合。题目：在或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的，请打印出这个所对应的字符的所有可能组合和组合数。四、实验过程以下程序都是在VS2010下编译与VC6.0代码稍有不同。（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。

8、题目分析依据题目可写出递归式：(F(n)-n)*6/7=F(n+1);F(n)是第n天奖牌总数即第n-1天剩余的包括第n天发的和剩下的。每天发放的金牌数：当天天数+（前一天剩余金牌-当天天数）/7，所以判别递归的条件是（前一天剩余金牌-当天天数）为7的整数倍，第i+1天的金牌数即i天剩下的必须是6的整数倍。算法构造递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7.筛选条件：(nSum(i,n)-i)%7=0&(nSum(i,n)%6=0)算法实现#include#define devide 7;/不知什么原因这样定义下面不能用？vc6.0未安上，不知与vs2010有和区别？

9、int nSum(int i,int n)/nSum()函数定义第i天的金牌数即i-1天剩下. int result=0;if(i=n) return n;elseresult=(nSum(i+1,n)*7)/6+i);/递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7.return result;void main()for(int n=2;n=10;n+)/递增比赛天数逐个验证int skip=0;for(int i=1;i=n;i+)/依次筛选从i=1到n符合条件的n值if(nSum(i,n)-i)%7=0&(nSum(i,n)%6=0)/每天发放的金牌数：当天天数+

10、（前一天剩余金牌-当天天数）/7，即（前一天剩余金牌-当天天数）为7的整数倍 int skip=1; /递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7即nSum(i,n)=nSum(i+1,n)*7/6+i，第i+1天的金牌数即i天剩下的必须是6的整数倍printf(共有金牌%d枚,共进行%d天n,nSum(1,n),n);/金牌总数即第一天金牌数 for(int j=1;j=n;j+) printf(第%d天,发放%d+%d枚,还剩%d枚n,j,j,(nSum(j,n)-j)/7,(nSum(j,n)-j)*6/7); break; if(skip=1)/用于跳出双层循

11、环结构即n递增时第一个满足时即可输出，可运行结果却不然break;/会有在n上界更多的结构输出，只有第一个n值满足不知为何？getchar();运行结果经验归纳递归式容易想出，但是相对的筛选条件比较难确定。（2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？题目分析这道国王分财产的题和上题运动会发金牌类似，不过在筛选条件仅

12、由题意略不同其实质也是一样，每个儿子分到的财产相同即：E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)，且第i个儿子分i份与剩下的1/10，即E(i,n)-i的差是10的整数倍。算法构造递归函数：E(i+1,n)=(E(i,n)-n)*9/10;E(i,n)为当要分给第i个儿子时还有的份数；筛选条件：每个儿子分到的财产相同即E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)；且第i个儿子分i份与剩下的1/10，即E(i,n)-i的差是10的整数倍。算法实现#include#define devide 10;/这样定义到后面不知怎么却出错。int E(int i,int

13、 n)/递归函数：E(i+1,n)=(E(i,n)-n)*9/10;E(i,n)为当要分给第i个儿子时还有的份数；int sum=0;if(i=n)return n;/当份到最后一个儿子时分完，往前求解；elsesum=(E(i+1,n)*10)/9+i;/依次递归；return sum;void main()for(int n=3;n=10;n+)int skip=0;for(int i=2;in;i+) /每个儿子分到的财产相同即E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)；/且第i个儿子分i份与剩下的1/10，即E(i,n)-i的差是10的整数倍；if(2*E(i,n)

14、-E(i-1,n)-E(i+1,n)=0)&(E(i,n)-i)%10=0)/用这两个条件筛选；int skip=1;printf(国王共有%d个儿子,财产共分成%d份。n,n,E(1,n);/总份数即要分第一个儿子时有的分数E(1,n)for(int j=1;j=n;j+)printf(第%d个儿子，分%d+%d份，还剩%d份。n,j,j,(E(j,n)-j)/10,(E(j,n)-j)*9/10);break;if(skip=1)break;getchar();运行结果经验归纳由于和第一题类似，此题较为顺利，类似多练习也会得心应手。（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金

15、鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？题目分析与上题类似出口为第四次买之前还有减去第四次买的还有11条。算法实现#include#define n 4;int Fish(int i)/构造函数Fish(i)为第i天卖之前还剩多少，Fish(1)即为总鱼数；int result=0;if(i4)result=(Fish(i+1)+(Fish(i+1)+1)/i);elsereturn 14;/第四天卖之

16、前的-第四天卖的=11，即Fish(4)-(Fish(4)/5+1/5)=11,F(4)=11return result;void main()printf(共有金鱼%d条。n,Fish(1);for(int i=1;i=4;i+)printf(第%d天,卖%d条，还剩%d条。n,i,(Fish(i)+i)/(i+1),(Fish(i)-(Fish(i)+i)/(i+1);getchar();运行结果经验归纳：以上题目类似可类比做出。4.某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都

17、先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？题目分析此题与以上几题类似，略有不同而已。算法构造由于从第一站出发没有任何变动，故将第二站作为始发站；函数Bus(i)为到达第i站还未上下乘客时车上人员数量；算法实现#includeint Bus(int i)/由于从第一站出发没有任何变动，故将第二站作为始发站； /函数Bus(i)为到达第i站还未上下乘客时车上人员数量；int sum=0;if(i6)/sum=2*(Bus(i+1)+i-7);/有递归函数：Bus(i+1)=Bus(i)/2+7-i;elsereturn 10;/由最后

18、还剩6人推的Bus(6)=10;return sum;void main()printf(发车时车上共有%d人。n,Bus(1);for(int i=1;i6;i+)printf(第%d站,上来%d人,下去%d人,剩下%d人n,i+1,(7-i),(Bus(i)/2),Bus(i+1);getchar();运行结果（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？题目分析与上题类似算法构造递推函数Monkey(i)表示第i天吃的和剩下的和；由Monkey(i+1)=Monkey(i)/2-1推

19、得；由Monkey(9)=Monkey(9)/2+1,得出口Monkey(9)=2。算法实现#includeint Monkey(int i)/递推函数Monkey(i)表示第i天吃的和剩下的和；int sum=0;if(i9)sum=2*(Monkey(i+1)+1);/由Monkey(i+1)=Monkey(i)/2-1推得；elsereturn 2;/由Monkey(9)=Monkey(9)/2+1,得出口Monkey(9)=2;return sum;void main()printf(共有桃子%d个。n,Monkey(1);for(int i=1;i=9;i+)printf(第%d天，

20、吃%d+%d个，剩下%d个。n,i,Monkey(i)/2,1,Monkey(i)/2-1);getchar();运行结果（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少页？题目分析与以上题目类似。算法构造构造递推函数：Book(i);表示第i天要读时还剩的页数；由Book(i+1)=Book(i)-(Book(i)/2+2)得出；由Book(5)-(Book(5)+2)=3可得出口；算法实现#includeint Book(int i)/构造递推函数：Book(i);表示第i天要读时还剩的页数；int sum=0;if

21、(i5)sum=2*(Book(i+1)+2);/由Book(i+1)=Book(i)-(Book(i)/2+2)得出；elsereturn 10;/由Book(5)-(Book(5)+2)=3可得出口；return sum;void main()printf(全书共%d页。n,Book(1);for(int i=1;i=5;i+)printf(第%d天，看%d+%d页，还剩%d页。n,i,Book(i)/2,2,Book(i)/2-2);getchar();运行结果（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的

22、1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？题目分析由老大开始分给老二，当老大拿到老六的后总数达到平均数，以此为入口进行递推。算法构造第一个孩子从国王那里分到的桔子总数应为平均数减去最后一个孩子分出去的部分后乘以8/7。算法实现#include #define DENOMINATOR_MAX 8 /分母最大值#define DENOMINATOR_MIN 3/分母最

23、小值/ai0表示第i个孩子分出的桔子总数/ai1表示第i个孩子从国王那里分到的桔子总数 int Orange(int a52,int i) int average=2520/6; 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_MI

24、N-1); else /第i个孩子从国王那里分到的桔子总数。 ai1 = average *(DENOMINATOR_MAX-i)/(DENOMINATOR_MAX-1-i) - Orange(a,i-1); /第i个孩子分给第i+1个孩子的桔子数量。 ai0 = ai1 + Orange(a,i-1) - average; p=ai0; return p; /主函数 void main() int ora52=0,0,0,0,0,0,0,0,0,0; Orange(ora,5); for(int j=0;j=5;j+) printf(第%d个孩子分出%d个橘子。n,j+1,oraj0); p

25、rintf(国王最初分配桔子状况如下所示：n); for(int k=0;k=5;k+) printf(第%d个孩子从国王那里分得%d个橘子。n,k+1,orak1); getchar(); 运行结果（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。题目分析第n天的病总人数包括n-1天潜伏的和发作的在当天又传染的人数再去掉当天治愈的；算法构造递推函数：该病五天潜伏第六天发病后五天治愈。Day(n)=Day(n-5)*3+Day(n-1);算法实现#include#includeint Da

26、y(int n)/递推函数：该病五天潜伏第六天发病后五天治愈。int sum=0;if(n=5)/五天只有一个潜伏病人。return 1;elsesum=Day(n-5)*3+Day(n-1);/第n天的病总人数包括n-1天潜伏的和发作的在当天又传染的人数再去掉当天治愈的； /Day(n)=Day(n-5)*3+Day(n-1);return sum;void main()int nprintf(请输入传染病发生后的天数：n);scanf_s(%d,&n,2);for(int i=1;i=n;i+)printf(第%d天,得病的人数%dn,i,Day(i);system(pause);运行结果

27、选做题：（5选3）（4）50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？题目分析这道题让我想到高中时做过的同样的一道排列组合题，但此题要用计算机编程求出具体数字，不像高中时只用代数式表达。算法构造假设为20阶：C（0 20）+ C（1 19）+ C（2 18）+ C（3 17）+ C（4 16）+ C（5 15）+ C（6 14）+ C（7 13）+ C（8 12）+ C（9 11）+ C（10 10）算法实现#include#includeint stairs(int n)if(n=1)return 1;if(n=0)return 1;return stairs(n-1)+sta

28、irs(n-2);/根据有1阶依次往上递推发现符合斐波那契数列 /an=an-1+an-2void main()int j;printf(请输入楼梯阶数：n);scanf_s(%d,&j,2);for(int i=1;i=j;i+)printf(当有%d阶楼梯,共有%d种走法。n,i,stairs(i);system(pause);运行结果数据可能过大或者电脑太low等了几分钟未见结果，根据后几阶时可判断是对的。经验归纳有些题看似困难当理清思路也可有据可循。（2）递归将一个整数输出。形如654321，输出1,2,3,4,5,6题目分析将一个整数逆序输出可以看做把一个字符串逆序输出，用指针逐个输

29、出。算法构造reverse(constchar *p)字符串递推函数：设定字符串指针*p；算法实现程序源代码#includevoid reverse(const char *p)/字符串递推函数：设定字符串指针*p；if(*p=0)/指针从右向左移动由于判断字符串尾部位置；return;reverse(p+1);/指针向前移动p+1printf(%c，,*p);/输出当前指针指向的字符；void main()char *pString;pString=123456;printf(输入的字符串：%sn,pString);reverse(pString);getchar();运行结果经验归纳巧用字

30、符串指针可以简化程序。（3）用递归实现分解质因数。形如：12=2*2*3题目分析质因数n即只能被本身和1整除的数，在2到n-1间筛选能被n整除且是质因数的数即可分解。算法构造bool IsPrime(int num)/判断质因数；if(IsPrime(i)&( num % i = 0 )/判断除数是否为质因数；num = num / i;PrimeFactorization(num);若是其一则保留对剩下的商继续判别；算法实现#include #include/质因数判断函数bool IsPrime(int num)/判断质因数； int i; for (i = 2; i num; i+) i

31、f ( num % i = 0 )/如果从2到num-1的数里有能被整除的，说明num不是质因数。return false; /如果从2到num-1的数里没有能被整除的，说明num是质因数。 return true; void PrimeFactorization(int num) int i;for (i=2; i=num; i+) if(i = num)printf(%d,i); else if(IsPrime(i)&( num % i = 0 )/质因数判断函数；/将找到的质因数追加到字符串中。printf(%d*,i);/将剩下部分递归分解。num = num / i;PrimeFactorization(num);break; void main() int num;printf(请输入一个小于10位的整数：n); scanf_s(%d,&num,10);printf(质因数分解：n%d=,num);/调用分解质因数函数。 PrimeFactorization(num);printf(n);system(pause);运行结果经验归纳弄清题目关键字的概念对编程很是关键。五、实验总结 编程蛮有意思，在这里能够格物致知看到不一样的世界。16 / 16