算法设计与分析递归算法典型例题

1、算法递归典型例题实验一：递归策略运用练习三、实验项目1.运用递归策略设计算法实现下述题目的求解过程。题目列表如下：(1) 运动会开了 N天，一共发出金牌 M枚。第一天发金牌 1枚加剩下的七分之一枚，第 二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第 N天刚好还有金牌 N枚，到此金牌全部发完。编程求 N和M。(2) 国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10;给第二个儿子两份，再加上剩余财产的1/10;；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的

2、偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序：(3) 出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？(4) 某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前

3、一站少一个 ，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？(5) 猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只，以此类推)，第九天正好吃完，问猴子们摘来了多少桃子？(6) 小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天 如此，第六天读完了最后的三页，问全书有多少页？(7) 日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子

4、分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？四、实验过程(一) 题目一：1. 题目分析由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一天的金牌剩余数，且每天的金牌数应为6的倍数。2. 算法构造设运动会举行了 N天， If(i=N)Goldi=N;Else goldi=goldi+1*7/6+i;/预编译命令/主函数/count表示运动会举办的天数定义储存数组3. 算法实现#include <iostream>using namespace

5、 std;void main()(int i=0,count=0;int gold100;do(count=count+6;/运动会天数加六goldcount=count; for (i=count-1; i>=1; i-) (if (goldi+1%6!=0) break; /跳出for循环 else goldi=goldi+1*7/6+i;计算第i天剩余的金牌数 while( i>=1 );/ 当 i>=1 继续做 do 循环cout <<"运动会开了 "<<count<<"天"<<

6、endl;/返回天数cout<<"总共发了 "<<gold1<<"枚金牌"<<endl;/返回金牌数(二) 题目二：1. 题目分析由已知可得，最后一个儿子得到的遗产份数即为王子数目，由此可得到每个儿子得到的 遗产份数，在对遗产数目进行合理性判断可得到符合要求的结果。2. 算法构造设皇帝有count个王子，propertycount=count;for (i=count-1; i>=1; i-)(/数目不符跳出for循环if (propertyi+1%9!=0)break;elsepropertyi=p

7、ropertyi+1*10/9+i;计算到第i个王子时剩余份数)3. 算法实现#include <iostream>/预编译命令using namespace std;void main() /主函数/count表示国王的儿子数定义储存数组,表示分配到每个王子时剩余份数/王子数目为9的倍数int i=0,count=0;int property100;docount=count+9;propertycount=count;for (i=count-1; i>=1; i-) if (propertyi+1%9!=0 ) break;/数目不符跳出for循环elsepropert

8、yi=propertyi+1*10/9+i; 计算到第i个王子时剩余份数) while( i>=1 );/ 当 i>=1 继续做 do 循环cout <<"皇帝有"<<count<<"个儿子"<< endl;/返回王子数cout<<"遗产被分成"<<property1<<"份”<<endl;返回遗产份数)4. 运行结果C:UsersDELL ,Desktop'，斯蓬*DebugC pp2.exeppmPi*es

9、s any key to continue(三) 题目三：1. 题目分析由最后一天的金鱼数目，可递推得到每天的金鱼数目，第一天的数目即为金鱼总数。2. 算法构造fish5=11;for (i=4; i>=1; i-)fishi=(fishi+1*(i+1)+1)/i;/计算到第i天剩余金鱼条数3. 算法实现#include <iostream>/ 预编译命令using namespace std;void main()/ 主函数int i=0;int fish6;fish5=11;for (i=4; i>=1; i-)定义储存数组各天剩余金鱼数fishi=(fishi+

10、1*(i+1)+1)/i;/计算到第i天剩余金鱼条数cout<<"浴缸里原有金鱼"<<fish1<<"条"<<endl;返总金鱼数4. 运行结果 C:Use rsD E LU Des kto p , >1 文件夹k De bu g'Cp p ?启烂苗缸里原有金鱼成条Press any 学 to continue(四) 题目四：1. 题目分析到第二站时车上的乘客数目有到终点站时车上的乘客数可求得到任意一站的乘客人数， 即为发车时车上的乘客数。2. 算法构造num8=6;到终点站车上还有六人for

11、(i=7; i>=2; i-)numi=2*(numi+1-8+i);计算到第i站车上的人数3. 算法实现#include <iostream>/ 预编译命令using namespace std;void main()/ 主函数 int i=0;int num9;/定义储存数组num8=6;到终点站车上还有六人for(i=7; i>=2; i-)numi=2*(numi+1-8+i);计算到第i站车上的人数cout<<"发车时车上有"<<num2<<"位乘客"<<endl;/返总发

12、站人数，即为到第二站时车上人数4. 运行结果r-qH C；UsersDELLDebLgCpp4.exe"发车时车上有"4位乘客.Press anv key to continue(五) 题目五：1.题目分析可假设有第十天，则第十天剩余的桃子数目为0,由此递推可得每一天剩余的桃子数目第一天的桃子数目即为猴子摘桃子的总数。2. 算法构造num10=0;/第n天吃前的桃子数for(i=9; i>=1; i-)3. 算法实现numi=2*(numi+1+1); 计算到第i天剩余的桃子数算法实现#include <iostream>/预编译命令using names

13、pace std;void main()/ 主函数int i=0;int num11;定义储存数组num10=0;/第n天吃前的桃子数for(i=9; i>=1; i-)numi=2*(numi+1+1);计算到第i天剩余的桃子数cout<<"猴子共摘来了 "<<num1<<"个桃子”<<endl;输出总的桃子数，即第一天吃前的数目4.运行结果(六) 题目六：1.题目分析由第六天剩余的页数可递推得到每天的剩余页数，第一天的页数即为全书的页数2. 算法构造num6=3;/到第n天时剩余的页数for(i=5; i&

14、gt;=1; i-)numi=2*(numi+1+2);计算到第i天剩余的页数3. 算法实现#include <iostream>/ 预编译命令using namespace std;void main()/ 主函数int i=0;int num7;/定义储存数组num6=3;/到第n天时剩余的页数计算到第i天剩余的页数for(i=5; i>=1; i-)numi=2*(numi+1+2);/输出总页数，即第一天吃前的数目cout<<"全书共有"<<num1<<"页"<<endl;)4.运

15、行结果Cpp6.exe"全书共有220页'Ppbs an9 key to cont inue（七）题目七：1. 题目分析由已知可得，第一个儿子得到的橘子数目为平均数的一半，由此可得到第一个儿子原先的橘子数目，而第i个儿子原先的橘子数目可由递推公式得到；2. 算法构造if(i=0)第一个儿子的数目/由left求第i+1个儿子的橘子数目第i+1个儿子得到的橘子数目(ai=(ave-ave/2)*(8-i)/(8-i-1);left=ai-ave/2;)else(ai=ave*(8-i)/(8-i-1)-left;left=ave/(8-i-1);)3. 算法实现#include&

16、lt;iostream>using namespace std;void main()(int a6;/存放六个儿子原先手中的橘子数目int left=0;存放下一个儿子得到的橘子数目int ave=420;for(int i=0;i<6;i+)(if(i=0)( ai=(ave-ave/2)*(8-i)/(8-i-1);第一个儿子的数目left=ai-ave/2;)else(ai=ave*(8-i)/(8-i-1)-left;/由 left 求第 i+1 个儿子的橘子数目left=ave/(8-i-1);/第i+1个儿子得到的橘子数目) ) for(i=0;i<6;i+) cout<<"第&qu