题解 | #不死神兔问题#

#include <iostream>
using namespace std;

int getSum(int n);
static int sum=0;

int main() {

    int n;
    cin >> n;

    cout << getSum(n) << endl;

    return 0;
}

int getSum(int n) {

    // // write your code here......
    // if(n==1||n==2)return 1;
    // int a=1;
    // int b=1;
    // int sum=0;
    // for(int i=3;i<=n;i++){
    //     sum=a+b;
    //     a=b;
    //     b=sum;
    // }
    // return sum;
    if(n<3)return 1;
    int sum=1;
    // for(int i=1;i<n-1;i++){
    //     sum+=getSum(i);
    // }
    for(int i=n-2;i>0;i--){
        sum+=getSum(i);
    }
    return sum;
}

该题有多种解决思路。

1.递归，发现规律是一个斐波那契数列。到n个月的兔子数量=n-1月的数量+n-2前兔子数量(生出的新兔子)

2.迭代，到n个月的兔子数量=n-1月的数量+n-2月兔子数量(每对生出一对新兔子)

3.总的兔子数量=（每对兔子+每对生的数量），以第一对兔子来看。n个月后会生出n-2对兔子+本身自己1对。再进行递归。sum+=getSum(i)