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

1、算法遞歸典型例題實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí)實(shí)驗(yàn)一：遞歸策略運(yùn)用練習(xí)三、三、實(shí)驗(yàn)項(xiàng)目實(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)分為若干份

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

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

4、猴王規(guī)定每天只準(zhǔn)吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問(wèn)猴子們摘來(lái)了多少桃子？（6）小華讀書。第一天讀了全書的一半加二頁(yè)，第二天讀了剩下的一半加二頁(yè)，以后天天如此……，第六天讀完了最后的三頁(yè)，問(wèn)全書有多少頁(yè)？（7）日本著名數(shù)學(xué)游戲?qū)＜抑写辶x作教授提出這樣一個(gè)問(wèn)題：父親將2520個(gè)桔子分給六個(gè)兒子。分完后父親說(shuō)：“老大將分給你的桔子的18給老二；老二拿到后連同原先的桔子分17給老三；老三拿到后連同原先的桔子

5、分16給老四；老四拿到后連同原先的桔子分15給老五；老五拿到后連同原先的桔子分14給老六；老六拿到后連同原先的桔子分13給老大”。結(jié)果大家手中的桔子正好一樣多。問(wèn)六兄弟原來(lái)手中各有多少桔子？四、四、實(shí)驗(yàn)過(guò)程實(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)Gold[i]=NEls

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