Question

猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦法，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個？用流程圖和偽代碼表示問題的算法．

Answer 1

答案：
解析：

解：我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫如下： 　　S1　a1←1；{第10天的桃子數(shù)，a1的初值} 　　S2　i←9；{計數(shù)器初值為9} 　　S3　a0←2×(a1＋1)；{計算當天的桃子數(shù)} 　　S4　a1←a0；{將當天的桃子數(shù)作為下一次計算的初值} 　　S5　i←i－1； 　　S6　若i≥1，轉(zhuǎn)S3； 　　S7　輸出a0的值； 　　偽代碼如下： 　　10　a1←1 　　20　i←9 　　30　a0←2×(a1＋1) 　　40　a1←a0 　　50　i←i－1 　　60　If i≥1 then Goto 30 　　70　Else 　　80　Print a0 　　流程圖如下： 　　思路分析：此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設第一天開始時有a1只桃子，第二天有a2只，…，第9天有a9只，第10天有a10只．在a1，a2，…，a10中，只有a10＝1是知道的，現(xiàn)要求a1，而我們可以看出a1，a2，…，a10之間存在一個簡單的關(guān)系： 　　a9＝2×(a10＋1)， 　　a8＝2×(a9＋1)， 　　…… 　　a1＝2×(a2＋1)． 　　也就是：ai＝2×(ai＋1＋1)i＝9，8，7，6，…，1． 　　這就是此題的數(shù)學模型． 　　再考察上面從a9，a8直至a1的計算過程，這其實是一個遞推過程，這種遞推的方法在計算機解題中經(jīng)常用到．另一方面，這九步運算從形式上完全一樣，不同的只是ai的下標而已．