算法設(shè)計(jì)與分析遞歸算法典型例題

1、算法遞歸典型例題實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí)三、實(shí)驗(yàn)項(xiàng)目1.運(yùn)用遞歸策略設(shè)計(jì)算法實(shí)現(xiàn)下述題目的求解過(guò)程。題目列表如下：(1) 運(yùn)動(dòng)會(huì)開(kāi)了 N天，一共發(fā)出金牌 M枚。第一天發(fā)金牌 1枚加剩下的七分之一枚，第 二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第 N天剛好還有金牌 N枚，到此金牌全部發(fā)完。編程求 N和M。(2) 國(guó)王分財(cái)產(chǎn)。某國(guó)王臨終前給兒子們分財(cái)產(chǎn)。他把財(cái)產(chǎn)分為若干份，然后給第一個(gè)兒子一份，再加上剩余財(cái)產(chǎn)的1/10;給第二個(gè)兒子兩份，再加上剩余財(cái)產(chǎn)的1/10;；給第i個(gè)兒子i份，再加上剩余財(cái)產(chǎn)的1/10。每個(gè)兒子都竊竊自喜。以為得到了父王的

2、偏愛(ài)，孰不知國(guó)王是“一碗水端平”的。請(qǐng)用程序回答，老國(guó)王共有幾個(gè)兒子？財(cái)產(chǎn)共分成了多少份？ 源程序：(3) 出售金魚(yú)問(wèn)題：第一次賣出全部金魚(yú)的一半加二分之一條金魚(yú)；第二次賣出乘余金魚(yú)的三分之一加三分之一條金魚(yú)；第三次賣出剩余金魚(yú)的四分之一加四分之一條金魚(yú)；第四次賣出剩余金魚(yú)的五分之一加五分之一條金魚(yú)；現(xiàn)在還剩下11條金魚(yú)，在出售金魚(yú)時(shí)不能把金魚(yú)切開(kāi)或者有任何破損的。問(wèn)這魚(yú)缸里原有多少條金魚(yú)？(4) 某路公共汽車，總共有八站，從一號(hào)站發(fā)軒時(shí)車上已有n位乘客，到了第二站先下一半乘客，再上來(lái)了六位乘客；到了第三站也先下一半乘客，再上來(lái)了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來(lái)了乘客比前

3、一站少一個(gè) ，到了終點(diǎn)站車上還有乘客六人，問(wèn)發(fā)車時(shí)車上的乘客有多少？(5) 猴子吃桃。有一群猴子摘來(lái)了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只(即第二天吃剩下的一半加一只，以此類推)，第九天正好吃完，問(wèn)猴子們摘來(lái)了多少桃子？(6) 小華讀書(shū)。第一天讀了全書(shū)的一半加二頁(yè)，第二天讀了剩下的一半加二頁(yè)，以后天天 如此，第六天讀完了最后的三頁(yè)，問(wèn)全書(shū)有多少頁(yè)？(7) 日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問(wèn)題：父親將2520個(gè)桔子分給六個(gè)兒子。分完 后父親說(shuō)：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子

4、分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問(wèn)六兄弟原來(lái)手中各有多少桔子？四、實(shí)驗(yàn)過(guò)程(一) 題目一：1. 題目分析由已知可得，運(yùn)動(dòng)會(huì)最后一天剩余的金牌數(shù)gold等于運(yùn)動(dòng)會(huì)舉行的天數(shù)由此可倒推每一天的金牌剩余數(shù)，且每天的金牌數(shù)應(yīng)為6的倍數(shù)。2. 算法構(gòu)造設(shè)運(yùn)動(dòng)會(huì)舉行了 N天， If(i=N)Goldi=N;Else goldi=goldi+1*7/6+i;/預(yù)編譯命令/主函數(shù)/count表示運(yùn)動(dòng)會(huì)舉辦的天數(shù)定義儲(chǔ)存數(shù)組3. 算法實(shí)現(xiàn)#include <iostream>using namespace

5、 std;void main()(int i=0,count=0;int gold100;do(count=count+6;/運(yùn)動(dòng)會(huì)天數(shù)加六goldcount=count; for (i=count-1; i>=1; i-) (if (goldi+1%6!=0) break; /跳出for循環(huán) else goldi=goldi+1*7/6+i;計(jì)算第i天剩余的金牌數(shù) while( i>=1 );/ 當(dāng) i>=1 繼續(xù)做 do 循環(huán)cout <<"運(yùn)動(dòng)會(huì)開(kāi)了 "<<count<<"天"<<

6、endl;/返回天數(shù)cout<<"總共發(fā)了 "<<gold1<<"枚金牌"<<endl;/返回金牌數(shù)(二) 題目二：1. 題目分析由已知可得，最后一個(gè)兒子得到的遺產(chǎn)份數(shù)即為王子數(shù)目，由此可得到每個(gè)兒子得到的 遺產(chǎn)份數(shù)，在對(duì)遺產(chǎn)數(shù)目進(jìn)行合理性判斷可得到符合要求的結(jié)果。2. 算法構(gòu)造設(shè)皇帝有count個(gè)王子，propertycount=count;for (i=count-1; i>=1; i-)(/數(shù)目不符跳出for循環(huán)if (propertyi+1%9!=0)break;elsepropertyi=p

7、ropertyi+1*10/9+i;計(jì)算到第i個(gè)王子時(shí)剩余份數(shù))3. 算法實(shí)現(xiàn)#include <iostream>/預(yù)編譯命令using namespace std;void main() /主函數(shù)/count表示國(guó)王的兒子數(shù)定義儲(chǔ)存數(shù)組,表示分配到每個(gè)王子時(shí)剩余份數(shù)/王子數(shù)目為9的倍數(shù)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;/數(shù)目不符跳出for循環(huán)elsepropert

8、yi=propertyi+1*10/9+i; 計(jì)算到第i個(gè)王子時(shí)剩余份數(shù)) while( i>=1 );/ 當(dāng) i>=1 繼續(xù)做 do 循環(huán)cout <<"皇帝有"<<count<<"個(gè)兒子"<< endl;/返回王子數(shù)cout<<"遺產(chǎn)被分成"<<property1<<"份”<<endl;返回遺產(chǎn)份數(shù))4. 運(yùn)行結(jié)果C:UsersDELL ,Desktop'，斯蓬*DebugC pp2.exeppmPi*es

9、s any key to continue(三) 題目三：1. 題目分析由最后一天的金魚(yú)數(shù)目，可遞推得到每天的金魚(yú)數(shù)目，第一天的數(shù)目即為金魚(yú)總數(shù)。2. 算法構(gòu)造fish5=11;for (i=4; i>=1; i-)fishi=(fishi+1*(i+1)+1)/i;/計(jì)算到第i天剩余金魚(yú)條數(shù)3. 算法實(shí)現(xiàn)#include <iostream>/ 預(yù)編譯命令using namespace std;void main()/ 主函數(shù)int i=0;int fish6;fish5=11;for (i=4; i>=1; i-)定義儲(chǔ)存數(shù)組各天剩余金魚(yú)數(shù)fishi=(fishi+

10、1*(i+1)+1)/i;/計(jì)算到第i天剩余金魚(yú)條數(shù)cout<<"浴缸里原有金魚(yú)"<<fish1<<"條"<<endl;返總金魚(yú)數(shù)4. 運(yùn)行結(jié)果 C:Use rsD E LU Des kto p , >1 文件夾k De bu g'Cp p ?啟爛苗缸里原有金魚(yú)成條Press any 學(xué) to continue(四) 題目四：1. 題目分析到第二站時(shí)車上的乘客數(shù)目有到終點(diǎn)站時(shí)車上的乘客數(shù)可求得到任意一站的乘客人數(shù)， 即為發(fā)車時(shí)車上的乘客數(shù)。2. 算法構(gòu)造num8=6;到終點(diǎn)站車上還有六人for

11、(i=7; i>=2; i-)numi=2*(numi+1-8+i);計(jì)算到第i站車上的人數(shù)3. 算法實(shí)現(xiàn)#include <iostream>/ 預(yù)編譯命令using namespace std;void main()/ 主函數(shù) int i=0;int num9;/定義儲(chǔ)存數(shù)組num8=6;到終點(diǎn)站車上還有六人for(i=7; i>=2; i-)numi=2*(numi+1-8+i);計(jì)算到第i站車上的人數(shù)cout<<"發(fā)車時(shí)車上有"<<num2<<"位乘客"<<endl;/返總發(fā)

12、站人數(shù)，即為到第二站時(shí)車上人數(shù)4. 運(yùn)行結(jié)果r-qH C；UsersDELLDebLgCpp4.exe"發(fā)車時(shí)車上有"4位乘客.Press anv key to continue(五) 題目五：1.題目分析可假設(shè)有第十天，則第十天剩余的桃子數(shù)目為0,由此遞推可得每一天剩余的桃子數(shù)目第一天的桃子數(shù)目即為猴子摘桃子的總數(shù)。2. 算法構(gòu)造num10=0;/第n天吃前的桃子數(shù)for(i=9; i>=1; i-)3. 算法實(shí)現(xiàn)numi=2*(numi+1+1); 計(jì)算到第i天剩余的桃子數(shù)算法實(shí)現(xiàn)#include <iostream>/預(yù)編譯命令using names

13、pace std;void main()/ 主函數(shù)int i=0;int num11;定義儲(chǔ)存數(shù)組num10=0;/第n天吃前的桃子數(shù)for(i=9; i>=1; i-)numi=2*(numi+1+1);計(jì)算到第i天剩余的桃子數(shù)cout<<"猴子共摘來(lái)了 "<<num1<<"個(gè)桃子”<<endl;輸出總的桃子數(shù)，即第一天吃前的數(shù)目4.運(yùn)行結(jié)果(六) 題目六：1.題目分析由第六天剩余的頁(yè)數(shù)可遞推得到每天的剩余頁(yè)數(shù)，第一天的頁(yè)數(shù)即為全書(shū)的頁(yè)數(shù)2. 算法構(gòu)造num6=3;/到第n天時(shí)剩余的頁(yè)數(shù)for(i=5; i&

14、gt;=1; i-)numi=2*(numi+1+2);計(jì)算到第i天剩余的頁(yè)數(shù)3. 算法實(shí)現(xiàn)#include <iostream>/ 預(yù)編譯命令using namespace std;void main()/ 主函數(shù)int i=0;int num7;/定義儲(chǔ)存數(shù)組num6=3;/到第n天時(shí)剩余的頁(yè)數(shù)計(jì)算到第i天剩余的頁(yè)數(shù)for(i=5; i>=1; i-)numi=2*(numi+1+2);/輸出總頁(yè)數(shù)，即第一天吃前的數(shù)目cout<<"全書(shū)共有"<<num1<<"頁(yè)"<<endl;)4.運(yùn)

15、行結(jié)果Cpp6.exe"全書(shū)共有220頁(yè)'Ppbs an9 key to cont inue（七）題目七：1. 題目分析由已知可得，第一個(gè)兒子得到的橘子數(shù)目為平均數(shù)的一半，由此可得到第一個(gè)兒子原先的橘子數(shù)目，而第i個(gè)兒子原先的橘子數(shù)目可由遞推公式得到；2. 算法構(gòu)造if(i=0)第一個(gè)兒子的數(shù)目/由left求第i+1個(gè)兒子的橘子數(shù)目第i+1個(gè)兒子得到的橘子數(shù)目(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. 算法實(shí)現(xiàn)#include&

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