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

算法递归典型例题

实验一：递归策略运用练习

三、 实验项目

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给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？

四、 实验过程

（一） 题目一：

1. 题目分析

由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一天的金牌剩余数，且每天的金牌数应为6的倍数。 2. 算法构造

设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;

3. 算法实现

#include <iostream> // 预编译命令 using namespace std; void main() {

int i=0,count=0; //count表示运动会举办的天数

int gold[100]; //定义储存数组 {

count=count+6; // 运动会天数加六 gold[count]=count; for (i=count-1; i>=1; i--) {

if (gold[i+1]%6!=0 )

break; // 跳出for循环

gold[i]=gold[i+1]*7/6+i; //计算第i天剩余的金牌数 else

do

//主函数

}

} while( i>=1 ); // 当 i>=1 继续做do循环

cout <<"运动会开了"<<count<<"天"<< endl; //返回天数 cout<<"总共发了"<<gold[1]<<"枚金牌"<<endl; //返回金牌数 4. 运行结果

}

（二） 题目二：

1. 题目分析

由已知可得，最后一个儿子得到的遗产份数即为王子数目，由此可得到每个儿子得到的遗产份数，在对遗产数目进行合理性判断可得到符合要求的结果。 2. 算法构造

设皇帝有count个王子，

property[count]=count; for (i=count-1; i>=1; i--) {

if (property[i+1]%9!=0 ) else

break;

// 数目不符跳出for循环

property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数

}

3. 算法实现 #include <iostream> using namespace std; void main() {

int i=0,count=0; //count表示国王的儿子数

int property[100]; //定义储存数组，表示分配到每个王子时剩余份数 do {

count=count+9; //王子数目为9的倍数

property[count]=count; for (i=count-1; i>=1; i--) {

if (property[i+1]%9!=0 ) else

property[i]=property[i+1]*10/9+i; //计算到第i个王子时剩余份数 break;

// 数目不符跳出for循环 //主函数

// 预编译命令

}

} while( i>=1 ); // 当 i>=1 继续做do循环

cout <<"皇帝有"<<count<<"个儿子"<< endl; //返回王子数 cout<<"遗产被分成"<<property[1]<<"份"<<endl; //返回遗产份数 4. 运行结果

}

（三）题目三：

1. 题目分析

由最后一天的金鱼数目，可递推得到每天的金鱼数目，第一天的数目即为金鱼总数。 2. 算法构造 fish[5]=11; for (i=4; i>=1; i--)

fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 3. 算法实现

#include <iostream> // 预编译命令 using namespace std; void main() {

int i=0;

//主函数

int fish[6]; //定义储存数组各天剩余金鱼数 fish[5]=11; for (i=4; i>=1; i--) }

4. 运行结果

fish[i]=(fish[i+1]*(i+1)+1)/i; //计算到第i天剩余金鱼条数 cout<<"浴缸里原有金鱼"<<fish[1]<<"条"<<endl; //返总金鱼数

（四）题目四： 1. 题目分析

有到终点站时车上的乘客数可求得到任意一站的乘客人数，到第二站时车上的乘客数目即为发车时车上的乘客数。 2. 算法构造

num[8]=6; //到终点站车上还有六人 for(i=7; i>=2; i--)

3. 算法实现

#include <iostream> // 预编译命令 using namespace std; void main() {

int i=0;

int num[9]; //定义储存数组 num[8]=6; //到终点站车上还有六人 for(i=7; i>=2; i--)

num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数

cout<<"发车时车上有"<<num[2]<<"位乘客"<<endl; //返总发站人数，即为到第二站时车上人数

}

4. 运行结果

//主函数

num[i]=2*(num[i+1]-8+i); //计算到第i站车上的人数

（五）题目五：

1. 题目分析

可假设有第十天，则第十天剩余的桃子数目为0，由此递推可得每一天剩余的桃子数目。第一天的桃子数目即为猴子摘桃子的总数。 2. 算法构造

num[10]=0; //第n天吃前的桃子数 for(i=9; i>=1; i--) 3. 算法实现

num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数算法实现

#include <iostream> // 预编译命令 using namespace std; void main() {

int i=0;

int num[11]; //定义储存数组 num[10]=0; //第n天吃前的桃子数 for(i=9; i>=1; i--) 的数目

}

4. 运行结果

num[i]=2*(num[i+1]+1); //计算到第i天剩余的桃子数

cout<<"猴子共摘来了"<<num[1]<<"个桃子"<<endl; //输出总的桃子数，即第一天吃前

//主函数

（六）题目六：

1. 题目分析

由第六天剩余的页数可递推得到每天的剩余页数，第一天的页数即为全书的页数 2. 算法构造

num[6]=3; //到第n天时剩余的页数 for(i=5; i>=1; i--)

num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数 3. 算法实现

#include <iostream> // 预编译命令 using namespace std; void main() { int i=0;

int num[7]; //定义储存数组 num[6]=3; //到第n天时剩余的页数 for(i=5; i>=1; i--)

num[i]=2*(num[i+1]+2); //计算到第i天剩余的页数

//主函数

cout<<"全书共有"<<num[1]<<"页"<<endl; //输出总页数，即第一天吃前的数目 }

4. 运行结果

（七）题目七： 1. 题目分析

由已知可得，第一个儿子得到的橘子数目为平均数的一半，由此可得到第一个儿子原先的橘子数目，而第i个儿子原先的橘子数目可由递推公式得到； 2. 算法构造

if(i==0)

3. 算法实现

#include<iostream> using namespace std; void main() {

int a[6]; //存放六个儿子原先手中的橘子数目 int left=0; //存放下一个儿子得到的橘子数目 int ave=420; for(int i=0;i<6;i++) {

if(i==0) { } else {

a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目 left=a[i]-ave/2; { } else { }

a[i]=ave*(8-i)/(8-i-1)-left; //由left求第i+1个儿子的橘子数目 left=ave/(8-i-1); //第i+1个儿子得到的橘子数目 a[i]=(ave-ave/2)*(8-i)/(8-i-1); //第一个儿子的数目 left=a[i]-ave/2;

}

}

a[i]=ave*(8-i)/(8-i-1)-left; //由left求第i+1个儿子的橘子数目 left=ave/(8-i-1); //第i+1个儿子得到的橘子数目

for(i=0;i<6;i++) }

4. 运行结果

cout<<"第"<<i+1<<"个儿子原先手中的的橘子数为"<<a[i]<<endl; //输出每个儿

子原先手中的橘子数目

本文来源：https://www.bwwdw.com/article/bdcj.html