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