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

: .
算法递归典型例题
实验一：递归策略运用练习
三、实验项目
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天，
lf(i==N)Gold[i]=N;
Else gold[i]=gold[i+1]*7/6+i;
3. 算法实现
#in elude <iostream> using n amespace std;
void mai n()
{
int i=0,cou nt=O;
int gold[100];
do
{
cou nt=cou nt+6; gold[cou nt]=cou nt; for (i=cou nt_1; i>=1; i--) {
if (gold[i+1]%6!=0 ) break; // 跳岀
//预编译命令
//主函数
//count表示运动会举办的天数
〃定义储存数组
//运动会天数加六
for循环
else
gold[i]=gold[i+1]*7/6+i; //计算第i天剩余的金牌数
}
} while( i>=1 ); // 当 i>=1 继续做 do 循环
cout <<"运动会开了 "<<count<<"天"<< endl; //返回天数
cout«"总共发了 "<vgold[1]vv"枚金牌"<<endl; //返回金牌数
}
4. 运行结果
word文档可自由复制编辑
word文档可自由复制编辑
(二) 题目二：……
1. 题目分析
由已知可得，最后一个儿子得到的遗产份数即为王子数目，由此可得到每个儿子得到的 遗产份数，在对遗产数目进行合理性判断可得到符合要求的结果。
2. 算法构造
设皇帝有count个王子，
property[cou nt]=cou nt;
for (i=cou nt-1; i>=1; i--)
{