每日经典算法题（十七） 猴子吃桃

猴子：Monkey 递归算法：Recursion Algorithm

题目

猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少个桃子？

程序分析

采取逆向思维的方法，从后往前推断，列出通项公式。

思路

通过题干我们可以得到基本信息是若有 n 个桃子，第一天则吃了 n/2 + 1 个桃子，即剩下 n/2 - 1 个桃子。

若假设某一天剩下的桃子数为 x，前一天剩下的桃子数为 y，根据上面的关系我们可以得到：
$$（x+1）\ast 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 打卡成功！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！