斐波那契小兔子c++

题目

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

分析
兔子的规律为数列为1,1,2,3,5,8,13,21….
规律：第三个数永远等于前两个数之和。

算法一：
由规律得出公式：从第三个数开始，f(n)=f(n-1)+f(n-2)
根据递归调用算法得出：

#include<iostream>
using namespace std;int f(int n){if(n==1||n==2) return 1;else return f(n-1)+f(n-2);
} int main(){int n; cout<<"请问想知道第几个月后的兔子总数呢？"<<endl; cin>>n;cout<<"第"<<n<<"个月的兔子总数为：";cout<<f(n)<<endl;
}

该算法可以得出一些小数目的答案，但却难以算出大数目结果。原因在于该程序的时间复杂度。

根据网上搜索查到的大概结论。时间复杂度是以2为底数呈指数增长的。可以运行试试，基本f(100)已经无法得出。（因为计算时间过长，这辈子都等不出来）。

算法二：利用循环算法

#include<iostream>
using namespace std;
int main(){int n;cout<<"请问想知道第几个月后的兔子总数呢？"<<endl; cin>>n;long long f[n]; f[1]=1;f[2]=1; if(n==1||n==2) f[n]=1;else{for(int i=3;i<=n;i++){f[i]=f[i-1]+f[i-2];}}cout<<"第"<<n<<"个月的兔子总数为：";cout<<f[n]<<endl;
}

由此时间复杂度减少为O(n)。可以算出100个月的兔子总数。注意存放兔子数组需要使用long long类型。

算法三：在时间复杂度相同的情况下，在算法二基础上对空间复杂度进行优化。使空间复杂度从O(n)变为O(1)。

#include<iostream>
using namespace std;
int fib(int n){int f0=0,f1=1,f2;for(int i=2;i<=n;i++){f2=f0+f1;f0=f1;f1=f2;}return f2;
} 
int main(){int n;cout<<"请问想知道哪个月小兔子的总数呢？"<<endl;cin>>n;cout<<"第"<<n<<"个月时，小兔子总数为："<<fib(n)<<"只。"<<endl; 
} 

多方学习，仅做参考留档。