【斐波那契数列】兔子繁殖问题

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

算法分析：

假设给兔子的对数编号

第一个月：1 , sum=1;
第二个月：1 ,sum=1;
第三个月：1生2,sum=2;

第四个月：1生3，2，sum=3;

第五个月：1生4，2生5，3，sum=5

第六个月：1生6，2生7，4，5，3生8，sum=8;

第七个月：1生9，6，2生10，7，3生11，8，3生11，4生12，5生13，sum=13;

....

经过以上分析，可以发现，后一想sum等于前两项sum之和，开始编程：

（1）递归形式

public class Main {
    
    public static int f(int n){
       if(n==1 || n==2){
           return 1;
       }
       else
           return f(n-1)+f(n-2);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        System.out.println(f(n));

    }

}

（2）迭代形式

public class Main {
    
    public static int f(int n)
    {
        int x1 = 1 ,x2 = 1,xn = 0;
        for(int i = 3 ; i <= n ; i++)
        {
            xn=x1+x2;
            x1=x2;
            x2=xn;
         
        }
        return xn;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        System.out.println(f(n));

    }

}