题目描述：已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后.第三个月开始生小兔子假如一年内没有发生死亡，则一对兔子开始，第N个月后会有多少对？
这道题所描述的就是斐波那契数列啦！这里以一对为单位，那么，从第一个月开始，每个月总共的兔子数量就是1,1,2,3,5,8,13......可以看出前两个月为1，从第三个月开始，当月的数量为前两个月数量之和，所以可以形成公式f(n)=f(n-1)+f(n-2)(n>2)同时f(1)=1,f(2)=1。
关于这道题的实现由很多种方法，那么接下来笔者就从O(2^n)说起。
1.时间复杂度O(2^n)
#include<iostream>
using namespace std;
int Fibonacci(int fib)
{
if(fib<=0)
{
return 0;
}
else if(fib==1||fib==2)
{
return 1;
}
else{
return Fibonacci(fib-1)+Fibonacci(fib-2);//当前月等于前一个月的数量加上前两个月的数量
}
}
int main()
{
int num,result;
cin>>num;//输入第几个月
result=Fibonacci(num);
cout<<result;
return 0;
}
下图描述了整个递归过程，可以看出最终形成了类似一个二叉树，每个节点都有访问，那么时间复杂度，就明显看的出来了
上图也同样暴露出上述递归算法的问题所在，就是同一个数多次访问，明明其它地方计算过了，却还会重复计算。
接下讲述另一种方法，时间复杂度有较大改善
2.时间复杂度O(n)
#include<iostream>
using namespace std;
int Fibonacci(int fib)
{
int res=1;
int pre=1;
int temp=0;
if(fib<=0)
{
return 0;
}
else if(fib==1||fib==2)
{
return 1;
}
else
{
for(int i=3;i<=fib;i++)
{
temp=res+pre;
pre=res;
res=temp;
}
return res;
}
}
int main()
{
int num,result;
cin>>num;//输入第几个月
result=Fibonacci(num);
cout<<result;
return 0;
}答案是肯定的。
3.时间复杂度O(log(n)) (本方法学习自牛客网，左程云(左神))
当然在讲述这种方法之前，必须要介绍一下线性代数的知识，在线性代数中下图中的等式是恒成立的。
#include<iostream>
using namespace std;
int base[4] = { 1, 1, 1, 0 };
int result[4] = { 1, 0, 0, 1 };//将结果矩阵初始为单位阵E
void MatrixMulti(int ba[4], int re[4], bool flag)// 这个函数实现其实应该用二维数组,原谅我这一生放纵不羁爱偷懒
{
int temp[4] = { 0 };
temp[0] = ba[0] * re[0] + ba[1] * re[2];
temp[1] = ba[0] * re[2] + ba[1] * re[3];
temp[2] = ba[2] * re[0] + ba[3] * re[2];
temp[3] = ba[2] * re[1] + ba[3] * re[3];
if (flag)
{
for (int i = 0; i < 4; i++)
{
result[i] = temp[i];
}
}
else
{
for (int i = 0; i < 4; i++)
{
base[i] = temp[i];
}
}
}
int main()
{
int month;
cin >> month;
if (month < 1)
{
cout << 0 << endl;
return 0;
}
if (month == 1||month==2)
{
cout << 1 << endl;
return 0;
}
month-=2;
for (; month != 0; month >>= 1)//此for循环是实现O(log(n))的关键
{
if (month & 1)
{
MatrixMulti(base, result,true);
}
MatrixMulti(base, base,false);
}
cout << result[0] + result[2];
return 0;
}#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void main()
{
double n;
scanf("%lf",&n);
printf("%d\n", (int)((pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n)) / sqrt(5)));
return 0;
}