《算法設計與分析》遞歸算法典型例題

1、算法遞歸典型例題實驗一：遞歸策略運用練習實驗一：遞歸策略運用練習三、三、實驗項目實驗項目1運用遞歸策略設計算法實現(xiàn)下述題目的求解過程。題目列表如下：（1）運動會開了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。（2）國王分財產(chǎn)。某國王臨終前給兒子們分財產(chǎn)。他把財產(chǎn)分為若干份

2、，然后給第一個兒子一份，再加上剩余財產(chǎn)的110；給第二個兒子兩份，再加上剩余財產(chǎn)的110；……；給第i個兒子i份，再加上剩余財產(chǎn)的110。每個兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是“一碗水端平”的。請用程序回答，老國王共有幾個兒子？財產(chǎn)共分成了多少份？源程序：（3）出售金魚問題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余

3、金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？（4）某路公共汽車，總共有八站，從一號站發(fā)軒時車上已有n位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個……，到了終點站車上還有乘客六人，問發(fā)車時車上的乘客有多少？（5）猴子吃桃。有一群猴子摘來了一批桃子，

4、猴王規(guī)定每天只準吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？（6）小華讀書。第一天讀了全書的一半加二頁，第二天讀了剩下的一半加二頁，以后天天如此……，第六天讀完了最后的三頁，問全書有多少頁？（7）日本著名數(shù)學游戲專家中村義作教授提出這樣一個問題：父親將2520個桔子分給六個兒子。分完后父親說：“老大將分給你的桔子的18給老二；老二拿到后連同原先的桔子分17給老三；老三拿到后連同原先的桔子

5、分16給老四；老四拿到后連同原先的桔子分15給老五；老五拿到后連同原先的桔子分14給老六；老六拿到后連同原先的桔子分13給老大”。結果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？四、四、實驗過程實驗過程（一）題目一：……1.題目分析由已知可得，運動會最后一天剩余的金牌數(shù)gold等于運動會舉行的天數(shù)由此可倒推每一天的金牌剩余數(shù)，且每天的金牌數(shù)應為6的倍數(shù)。2.算法構造設運動會舉行了N天，If(i==N)Gold[i]=NEls

6、egold[i]=gold[i1]76iproperty[i]=property[i1]109i計算到第i個王子時剩余份數(shù)3.算法實現(xiàn)#include預編譯命令usingnamespacestdvoidmain()主函數(shù)inti=0count=0count表示國王的兒子數(shù)intproperty[100]定義儲存數(shù)組，表示分配到每個王子時剩余份數(shù)docount=count9王子數(shù)目為9的倍數(shù)property[count]=countf(i