递推和递归的方法解决猴子吃桃问题（10天延伸到N天）——Java_猴子吃桃递推法

目录

问题重述

递推法

问题分析

递推代码部分

运行结果：

递归法

问题分析

递归代码部分

运行结果：

---

问题重述

猴子吃桃问题。

猴子第一天吃了若干个桃子，当即吃了一半，还不解馋，又多吃了一个； 第二天，吃剩下的桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问猴子第一天共摘了多少个桃子？

问题延伸到n天

卖桃子问题。某人摘下一些桃子，第一天卖掉一半，又吃了一个，第二天卖掉剩下一半，又吃了一个，以后天天都是如此处理，到第n天发现只剩下一个桃子，n是参数，返回值是一共摘的桃子数。

---

递推法

问题分析

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。

1. 所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。如斐波拉契数列。

1. 所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

从本题中可以看出，第n天桃子数是1，所以可以采用逆推的方法来推理，那么第n-1天的个数为（1+1）*2，第n-2天的个数就为（（1+1）*2 + 1）*2 。可以看出从后一天是可以推出前一天个数的，那么我们就可以用递推的方法，依次累加的个数就是第一天摘的桃子数，循环次数就是（n - 1)次。

递推代码部分

 public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     System.out.println("请输入天数");
     int n = scanner.nextInt();
     int Num = 1;
     int i;
     for (i = 1;i<n;i++){
         Num = (Num+1)*2;   //循环了（n-1）次
     }
     System.out.println("一共摘了"+Num+"个桃子");

运行结果：

 

---

递归法

问题分析

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

通过正向观察看出存在一个函数关系，那么第一天的数量可表示为f(1)=(f(2)+1)*2 ，第二天的数量就是 f(2)=(f(3)+1)*2 ，以此类推，第n - 1天的数量就是 f(n-1)=(f(n)+1)*2 。执行方法的次数是n。

递归代码部分

 public static void main(String[] args) {
 ​
     System.out.println("请输入天数");
     Scanner scanner = new Scanner(System.in);
     int x = scanner.nextInt();
     System.out.println("一共摘了"+F(1, x)+"个桃子");//如果想输入每一天的值，在上面加个for循环即可
 }
 static int F(int day, int x){  //day是这个方法的自循环量，x是把键盘键入的值放到这里
 
     if(day == x){    //键盘键入的天数肯定是最后一天，最后一天的是是1
         return 1;
     }else {
         return (F(day+1, x)+1)*2;
     }
 }

运行结果：

---

如果内容有错误，麻烦大家指出一下，有疑问的可以评论区留言（我会解答）。

觉得挺好的可以点赞和关注，谢谢大家