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

算法遞歸典型例題實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí)三、 實(shí)驗(yàn)項(xiàng)目1運(yùn)用遞歸策略設(shè)計(jì)算法實(shí)現(xiàn)下述題目的求解過程。題目列表如下： （1）運(yùn)動(dòng)會(huì)開了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è)兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國(guó)王是“一碗水端平”的。請(qǐng)用程序回答，老國(guó)王共有幾個(gè)兒子？財(cái)產(chǎn)共分成了多少份？源程序：（3）出售金魚問題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時(shí)不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？（4）某路公共汽車，總共有八站，從一號(hào)站發(fā)軒時(shí)車上已有n位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個(gè)，到了終點(diǎn)站車上還有乘客六人，問發(fā)車時(shí)車上的乘客有多少？（5）猴子吃桃。有一群猴子摘來了一批桃子，猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？（6）小華讀書。第一天讀了全書的一半加二頁(yè)，第二天讀了剩下的一半加二頁(yè)，以后天天如此，第六天讀完了最后的三頁(yè)，問全書有多少頁(yè)？（7）日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問題：父親將2520個(gè)桔子分給六個(gè)兒子。分完 后父親說：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結(jié)果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？四、 實(shí)驗(yàn)過程（一） 題目一：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;3. 算法實(shí)現(xiàn) #include <iostream> / 預(yù)編譯命令 using namespace std; void main() /主函數(shù) int i=0,count=0; /count表示運(yùn)動(dòng)會(huì)舉辦的天數(shù) int gold100; /定義儲(chǔ)存數(shù)組 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ì)開了"<<count<<"天"<< endl; /返回天數(shù) cout<<"總共發(fā)了"<<gold1<<"枚金牌"<<endl; /返回金牌數(shù) 4. 運(yùn)行結(jié)果（二） 題目二：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-) if (propertyi+1%9!=0 )break; / 數(shù)目不符跳出for循環(huán)elsepropertyi=propertyi+1*10/9+i; /計(jì)算到第i個(gè)王子時(shí)剩余份數(shù) 3. 算法實(shí)現(xiàn) #include <iostream> / 預(yù)編譯命令 using namespace std; void main() /主函數(shù) int i=0,count=0; /count表示國(guó)王的兒子數(shù) int property100; /定義儲(chǔ)存數(shù)組，表示分配到每個(gè)王子時(shí)剩余份數(shù) do count=count+9; /王子數(shù)目為9的倍數(shù) propertycount=count; for (i=count-1; i>=1; i-) if (propertyi+1%9!=0 )break; / 數(shù)目不符跳出for循環(huán)elsepropertyi=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é)果（三）題目三：1. 題目分析由最后一天的金魚數(shù)目，可遞推得到每天的金魚數(shù)目，第一天的數(shù)目即為金魚總數(shù)。2. 算法構(gòu)造fish5=11; for (i=4; i>=1; i-)fishi=(fishi+1*(i+1)+1)/i; /計(jì)算到第i天剩余金魚條數(shù)3. 算法實(shí)現(xiàn)#include <iostream> / 預(yù)編譯命令using namespace std;void main() /主函數(shù) int i=0; int fish6; /定義儲(chǔ)存數(shù)組各天剩余金魚數(shù) fish5=11; for (i=4; i>=1; i-)fishi=(fishi+1*(i+1)+1)/i; /計(jì)算到第i天剩余金魚條數(shù)cout<<"浴缸里原有金魚"<<fish1<<"條"<<endl; /返總金魚數(shù)4. 運(yùn)行結(jié)果（四）題目四：1. 題目分析有到終點(diǎn)站時(shí)車上的乘客數(shù)可求得到任意一站的乘客人數(shù)，到第二站時(shí)車上的乘客數(shù)目即為發(fā)車時(shí)車上的乘客數(shù)。2. 算法構(gòu)造num8=6; /到終點(diǎn)站車上還有六人for(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ā)站人數(shù)，即為到第二站時(shí)車上人數(shù)4. 運(yùn)行結(jié)果（五）題目五：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 namespace 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<<"猴子共摘來了"<<num1<<"個(gè)桃子"<<endl; /輸出總的桃子數(shù)，即第一天吃前的數(shù)目4. 運(yùn)行結(jié)果（六）題目六：1. 題目分析由第六天剩余的頁(yè)數(shù)可遞推得到每天的剩余頁(yè)數(shù)，第一天的頁(yè)數(shù)即為全書的頁(yè)數(shù)2. 算法構(gòu)造num6=3; /到第n天時(shí)剩余的頁(yè)數(shù)for(i=5; i>=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ù)for(i=5; i>=1; i-)numi=2*(numi+1+2); /計(jì)算到第i天剩余的頁(yè)數(shù)cout<<"全書共有"<<num1<<"頁(yè)"<<endl; /輸出總頁(yè)數(shù)，即第一天吃前的數(shù)目4. 運(yùn)行結(jié)果（七）題目七：1. 題目分析由已知可得，第一個(gè)兒子得到的橘子數(shù)目為平均數(shù)的一半，由此可得到第一個(gè)兒子原先的橘子數(shù)目，而第i個(gè)兒子原先的橘子數(shù)目可由遞推公式得到； 2. 算法構(gòu)造if(i=0)ai=(ave-ave/2)*(8-i)/(8-i-1); /第一個(gè)兒子的數(shù)目left=ai-ave/2;elseai=ave*(8-i)/(8-i-1)-left; /由left求第i+1個(gè)兒子的橘子數(shù)目left=ave/(8-i-1); /第i+1個(gè)兒子得到的橘子數(shù)目3. 算法實(shí)現(xiàn) #include<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;elseai=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<<"第"<<i+1<<"個(gè)兒子原先手中的的橘子數(shù)為"<<ai<<endl; /輸出每個(gè)兒子原先手中的橘子數(shù)目4. 運(yùn)行結(jié)果