猴子：Monkey 递归算法：Recursion Algorithm
题目猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少个桃子？
程序分析采取逆向思维的方法，从后往前推断，列出通项公式。
思路通过题干我们可以得到基本信息是若有 n 个桃子，第一天则吃了 n/2 + 1 个桃子，即剩下 n/2 - 1 个桃子。
若假设某一天剩下的桃子数为 x，前一天剩下的桃子数为 y，根据上面的关系我们可以得到：
（
x
+
1
）
∗
2
=
y
（x + 1）* 2 = y
（x+1）∗2=y
简单计算一下，我们已知最后一天剩 1 个，根据推算的公式可以得到倒数第二天剩下 4 个，同理根据递归算法即可求出第一天剩下多少个。
在这里需要注意的是，猴子是到第十天想吃（还没吃）的时候发现只剩一个了，所以循环的次数要注意是 9 次。
循环递归计算之后输出结果即可。若想查看每天的结果也可输出查看
代码示例public class Q17_Recursive_MonkeyPeaches {
public static void main(String[] args) {
int sum = 1;
for (int i =1;i<10;i++){
sum = (sum + 1) * 2;
System.out.print(sum+"t");
}
System.out.println("第一天一共摘了"+sum+"个。");
}
}
输出结果
4 10 22 46 94 190 382 766 1534 第一天一共摘了1534个。
- Day17 打卡成功！
