当前位置：文档库 › 《算法设计与分析》递归算法典型例题

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

算法递归典型例题

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

三、实验项目

1运用递归策略设计算法实现下述题目的求解过程。题目列表如下：

(1)运动会开了N天，一共发岀金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此

办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求

(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天，lf(i==N)Gold[i]=N;

Else gold[i]=gold[i+1]*7/6+i;

using n ames pace std; void mai nO {

int i=0,cou nt=O; int gold[100]; do

gold[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {

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

break; //跳岀for 循环 else

gold[i]=gold[i+1]*7/6+i;

//计算第i 天剩余的金牌数

题目二:

题目分析

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

算法构造

设皇帝有count 个王子，

prop erty[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {

if (prop erty[i+1]%9!=0 )

break;

〃数目不符跳岀for 循环

else

算法实现

#in elude

//预编译命令

{

cou nt=cou nt+6;

//运动会天数加六

//主函数 //cou nt 表示运动会举办的天数

//定义储存数组

}

} while( i>=1 );

cout <<"运动会开了 "<

运行结果

i>=1

继续做do 循环

//返回天数 //返回金牌数

}

3.算法实现

P ro perty[i]=prop erty[i+1]*10/9+i;

〃计算到第i 个王子时剩余份数

#in elude //预编译命令

using n ames pace std; void mai nO {

//主函数

int i=0,cou nt=0; int prop erty[100]; do //count 表示国王的儿子数

〃定义储存数组,

表示分配到每个王子时剩余份数 {

cou nt=cou nt+9;

prop erty[cou nt]=cou nt; for (i=cou nt-1; i>=1; i--) {

//王子数目为 9的倍数

if (prop erty[i+1]%9!=0 )

break;

//数目不符跳岀

else

for 循环

} 4.

}

} while( i>=1 );

// 当 i>=1

cout <<"皇帝有"<

//返回王子数

//返回遗产份数

运行结果

rs\ID E0_\ De s klo 箭建交件夹\ Deb uq\C pp

1.题目分析

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

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

#include // 预编译命令

using n ames pace std; void mai nO //主函数

int i=0;

P ro perty[i]=prop erty[i+1]T0/9+i;

〃计算到第i 个王子时剩余份数

int fish [ 6];

fish[5]=11;

for (i=4; i>=1; i--)

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

using n ames pace std; void

int i=0;

num[9];

num[8]=6;

for(i=7; i>=2; i--)

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

cout<<"发车时车上有"<

}

4.运行结果

Press anv key to continue

(五)题目五：?…

1.题目分析

〃定义储存数组各天剩余金鱼数

}

4. 运行结果

浴缸里原有金鱼59条.

Press any key to continite

(四)题目四：……

题目分析

有到终点站时车上的乘客数可求得到任意一站的乘客人数, 即

为发车时车上的乘客数。

算法构造

到第二站时车上的乘客数目

num[8]=6; for(i=7; i>=2; i--)

n um[i]=2*( num[i+1]-8+i);

//到终点站车上还有六人

〃计算到第i站车上的人数

3.算法实现

#in elude //预编译命令

//主函数

mai nO

//定义储存数组

//到终点站车上还有六人

int

可假设有第十天，则第十天剩余的桃子数目为 0 ,由此递推可得每一天剩余的桃子数目。

第一天的桃子数目即为猴子摘桃子的总数。

2. 算法构造

n um[10]=0; for(i=9; i>=1; i--) 3.算法实现

■iJ J 'C:\U5er^\DELL\De5ktop\^aS ：1W^Debug\Cpp5,exe

(六)题目六： .....

题目分析

由第六天剩余的页数可递推得到每天的剩余页数，第一天的页数即为全书的页数

算法构造

num[6]=3; for(i=5; i>=1; i--)

n um[i]=2* (n um[i+1]+2);

3.算法实现

//到第 n 天时剩余的页数

//计算到第i 天剩余的页数

#in clude

//预编译命令

using n ames pace std; void mai nO { int i=0;

//主函数

int n um[7]; num[6]=3; for(i=5; i>=1; i--)

n um[i]=2* (n um[i+1]+2);

//定义储存数组 //到第n 天时剩余的页数

//计算到第i 天剩余的页数

//第n 天吃前的桃子数

num[i]=2* (n um[i+1]+1);

〃计算到第i 天剩余的桃子数算法实现

#in elude //预编译命令

using n ames pace std; void

mai nO

//主函数

int i=0;

n um[11];

n um[10]=0;

for(i=9; i>=1; i--) num[i]=2*(num[i+1]+1);

//计算到第i 天剩余的桃子数

cout<<"猴子共摘来了 "<

//输岀总的桃子数，即第一天吃前

的数目

int

〃定义储存数组

//第n 天吃前的桃子数

}

运行结果

cout<<"全书共有"<

4.运行结果

se pp5. exe

(七)

2. 题目七：……

题目分析

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

算法构造

if(i==0)

{

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=ave/(8-i-1);

} //由left求第i+1个儿子的橘子数目//第i+1个儿子得到的橘子数目

3.算法实现

#in clude using n ames pace std;

void mai n()

{

int a[6];

int left=O;

int ave=420;

for(i nt i=0;i<6;i++) { //存放六个儿子原先手中的橘子数目〃存放下一个儿子得到的橘子数目

if(i==0)

{

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

}

else