Question

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

Answer 1

答案：
解析：

解：本題的算法如下： 　　第一步：a1←1；{第10天的桃子數(shù)，a1的初值} 　　第二步：i←9；{計數(shù)器初值為9} 　　第三步：a0←2×(a1＋1)；{計算當天的桃子數(shù)} 　　第四步：a1←a0；{將當天的桃子數(shù)作為下一次計算的初值} 　　第五步：i←i－1； 　　第六步：若i≥1，轉(zhuǎn)第三步； 　　第七步：輸出a0的值． 　　偽代碼如下： 　　a1←1 　　i←9 　　If i≥1 Then 　　a0←2×(a1＋1) 　　a1←a0 　　i←i－1 　　End If 　　Print　a0 　　流程圖如下圖所示： 　　分析：此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設第一天開始時有a1只桃子，第二天有a2只，…，第9天有a9只，第10天有a10只．在a1，a2，…，a10中，只有a10＝1是知道的，現(xiàn)要求a1，而我們可以看出a1，a2，…，a10之間存在一個簡單的關系： 　　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的下標而已．由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)．

提示：

這類題的解法是一個從具體到抽象的過程，具體方法是： 　　(1)弄清如果由人來做，應該采取哪些步驟； 　　(2)對這些步驟進行歸納整理，抽象出數(shù)學模型； 　　(3)對其中的重復步驟，通過使用相同變量等方式求得形式的統(tǒng)一，然后簡練地用循環(huán)解決．