运用递归策略设计算法

《运用递归策略设计算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学号《算法设计与分析》实验报告一学生姓名专业、班级指导教师成绩系2011年9月22日运用递归策略设计算法实现下述题目的求解过程。题目列表如下：（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。1.题目分析与算法构造在此论证算法设计中的一些必要的设计依据。首先要找出递推规律f[i-1]=f[i]*7/6+(i-1);发现每天发

2、放的金牌数必须为6的倍数，由此而知n=n+6;到了第N天刚好还有金牌N枚f[n]=n;再用for循环递推得出得出共有金牌数M：f[1]块。2.算法实现程序源代码（请写入必要的注释）。#includeusingnamespacestd;intmain(){inti=0;intn=0;intf[20];n=n+6;f[n]=n;for(i=n;i>=1;i--){f[i-1]=f[i]*7/6+(i-1);}cout<<"共有金牌数M："<

3、<<”N”<

4、推公式f[i-1]=10/9*f[i]+i-1;因为财产全部平均分完，所以给第i个儿子分完后就没有剩余了，因为国王是“一碗水端平”的，所以每个儿子都是i份。总财产就是代码中的n*n。（n为儿子个数）2.算法实现程序源代码（请写入必要的注释）。#includeusingnamespacestd;intmain(){inti,n=0;n=+9;intf[20];f[n]=n;for(i=n;i>0;i--){f[i-1]=10/9*f[i]+i-1;}cout<<"老国王共有"<

5、<<"儿子"<

6、设计中的一些必要的设计依据。首先找出递归公式f[i-1]=(f[i]*i+1)/(i-1);要知道第一次卖完剩下的金鱼，就是第二次没有做任何变动的金鱼数。所以第四次卖完剩下的金鱼数量就写成f[5]。根据for循环即可得出结论。2.算法实现程序源代码（请写入必要的注释）。#includeusingnamespacestd;intmain(){intf[6];inti;f[5]=11;for(i=5;i>=2;i--){f[i-1]=(f[i]*i+1)/(i-1);}cout<<"

7、鱼缸里原有金鱼："<

8、;下一站的初始人数就是前一站的剩余人数。到了终点站车上还有乘客六人，总共有八站,f[8]=6;2算法实现程序源代码（请写入必要的注释）。#includeusingnamespacestd;intmain(){intf[9];f[8]=6;inti;for(i=8;i>1;i--){f[i-1]=2*(f[i]-(8-(i-1)));}cout<<"第1站有乘客："<