[每日一道小算法（七十四）][递归] 兔子繁衍（奇安信笔试题）

偏执的太偏执、 2023-07-09 12:26 69阅读 0赞

前言：  
今天参加了奇安信春招的笔试题，两道算法题，就会一道，还没全AC。唉，算法能力太差了。还得继续努力呀！！！！

### 题目描述 ###

有一对兔子，从出生后的第五个月起每月生出一对小兔子（即满4月就开始生小兔），小兔子也会出生从第五个月起每月生一对小兔子。假如兔子不会死，第n个月时，兔群有多少对兔子。  
输入描述：  
第n个月（n为自然数，n<101）  
输出描述：  
第n个月时，兔子的对数（兔群的兔子有多少对兔子）

示例1：  
输入：  
5

输出：  
2

### 解题思路 ###

这道题，最开始我也是没有思路，我就开始从第一个月开始进行，列举，然后找规律。还真找出规律来了。  
从第一个月开始，有多少对兔子我们列举：  
1，1，1，1，2，3，4，5，7，10…  
通过这个我就可以发现，我们可以使用递归来实现。  
![在这里插入图片描述][20200228215252665.png]  
根据递归，我们就可以写代码了。

### 解题思路 ###

package QiAnXin;
    
    
    import java.util.Scanner;
    
    public class Main2 { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext())
            { 
                int n = scanner.nextInt();
                int result = Rabbit(n);
                System.out.println(result);
            }
        }
        public static int Rabbit(int n)
        { 
            if(n<5)
            { 
                return 1;
            }
           return Rabbit(n-1) + Rabbit(n-4);
        }
      
    }

[20200228215252665.png]: https://img-blog.csdnimg.cn/20200228215252665.png