简单的方法递归题

迷南。 2021-09-25 06:06 263阅读 0赞

### 文章目录 ###

*  题目1：卖鸭子
 *  题目2：不死神兔

# 题目1：卖鸭子 #

一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？

*  解题思路:用数学思想解决此类问题比较简单。此题是知道还剩下多少鸭子，不知道一开始有多少鸭子，为知尾不知头的类型。所以我们要寻找F(n)与F(n+m)的规律，m是题中数据发生显著变化的间隔，本题m=1，因为每经过1个村子，数据就会发生变化。
 *  设一个函数F(n),F为经过n个村子后鸭子的数量，n为第n个村子
 *  从题中我们可以得知F(7)=2
 *  所剩下的2只鸭子是经过6个村子后卖剩下的，F(6) - F(6)/2 -1 = F(7)
 *  换算一下 得出 F(6) = 2(F(7)+1)
 *  依次逻辑类推F(5) = 2(F(4)+1)
 *  最后得到F(n) = 2(F(n+1)+1)
 *

public class Duck { 
        public static void main(String[] args) { 
        //实参为0,经过0个村子剩下的鸭子数量就是我们出发时的鸭子数量
            int i = countDuck(0);
            System.out.println(i);
            //经过0个村子的鸭子数量减去经过1个村子的鸭子数量，就是第一个村子卖出的鸭子数量
            int duck =countDuck(0)-countDuck(1);
            System.out.println("第1个村子卖出了鸭子的数量"+duck);
        }
        //定义数鸭子的方法
        public static int countDuck(int village){ 
            if(village == 7){ 
                return  2;
            }else { 
                return  (countDuck(village+1)+1)*2;
            }
        }
    }

程序运行结果

510
    第1个村子卖出了鸭子的个数256

# 题目2：不死神兔 #

有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

*  解题思路:用数学思想解决此类问题比较简单。此题是知道开始有几对兔子，不知道后来有多少兔子，为知头不知尾的类型。所以我们要寻找F(n)与F(n-m)的规律，m是题中数据发生显著变化的间隔，本题m=1和2，因为每对兔子的出生时间不同，长成大兔子的间隔也不统一。
 *  为了方便我们对本题数据的认识，将对每对兔子进行编号，用于区分。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h5cGVydGV4dDEyMw_size_16_color_FFFFFF_t_70_pic_center]  
    从图中我们可以发现规律，第3个月的兔子对数等于第2个月加上第1个月的，即F(3) = F(2) + F(1)  
    F(4) = F(3) + F(2)，总结出规律 F(n) = F(n-1) + F(n-2)  
    代码实现:

public class Rabbit { 
        public static void main(String[] args) { 
        //求第4个月的兔子对数
            int i = countRabbit(4);
            System.out.println(i);
        }
        //定义方法，数兔子
        public static int countRabbit(int month){ 
              if(month ==1 || month ==2){ 
                  return 1;
              }else { 
                  return countRabbit(month-1) + countRabbit(month -2)  ;
              }
        }
    }

程序运行结果

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h5cGVydGV4dDEyMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/be6b73b2732c405dafcd05d0cd533e62.png