社团活动｜python猴子吃桃

梦回唐朝

猴子吃桃问题描述

有一只猴子，第一天摘了若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天它把剩下的桃子又吃了一半，再多吃一个。以后每天都是这样吃，到第n天的时候，只剩下1个桃子了。要求通过算法计算出最初猴子摘了多少个桃子。

算法思路

可以采用倒推的方法来解决这个问题。从已知的最后一天剩下1个桃子开始，逐步往前推算每一天桃子的数量。

设第 i 天桃子的数量为 x[i] ，已知第 n 天桃子数量 x[n] = 1 。

对于第 n - 1 天，因为这天吃完后剩下的就是第 n 天的数量，根据吃桃规则倒推可得： x[n - 1] = (x[n] + 1) * 2 。
　　
同理，对于第 i 天（ i 从 n - 1 递减到 1 ），其桃子数量的递推公式为： x[i] = (x[i + 1] + 1) * 2 。