多种方法求斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
在C++中可以有多种方法求斐波那契数列

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数k，要求菲波那契数列中第k个数是多少。
题目链接：
OpenJudge NOI 1.5 17:菲波那契数列

设置变量n2，n1，表示当前已知的倒数第二项，和最后一项求新的项t，t = n1 + n2;新的倒数第二项是原来的最后一项，所以使n2 = n1;t将会是新的最后一项，有n1 = t;i为3时求出第3项，i为4时求出第4项，i为k时求出第k项。循环i从3循环到k，即可求出第k项

时间内复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( 1 ) O(1) O(1)

#include
using namespace std;
int main()
{
	int k, n2 = 1, n1 = 1, t;//n2,n1是当前求出的倒数第二项，和最后一项 
	cin >> k;
	for(int i = 3; i <= k; ++i)
	{
		t = n1 + n2;
		n2 = n1;
		n1 = t;
	}
	cout << n1;
	return 0;
}

递推状态：a[i]为斐波那契数列第i项递推关系：斐波那契数列第i项为其前两项之和，即a[i] = a[i-1]+a[i-2]初始状态：第1项与第2项值为1

时间内复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( n ) O(n) O(n)

#include
using namespace std;
int main()
{
	int k, a[50];//a[i]为斐波那契数列第i项
	a[1] = a[2] = 1;
	cin >> k;
	for(int i = 3; i <= k; ++i)
		a[i] = a[i-1] + a[i-2];
	cout << a[k];
	return 0;
}

递归问题：求斐波那契数列第k项递归关系：想要求第k项，必须先求第k-1项和第k-2项，而后将这两项加和递归出口：斐波那契数列第1和第2项为1

时间内复杂度： O ( 2 n ) O(2^n) O(2n)，空间复杂度： O ( n ) O(n) O(n)

#include
using namespace std;
int fib(int k)//求斐波那契数列第k项 
{
	if(k == 1 || k == 2)
		return 1;
	else
		return fib(k - 1) + fib(k - 2);
}
int main()
{
	int k;
	cin >> k;
	cout << fib(k);
	return 0;
}

同一种思路，用栈将递归转为非递归写法

#include
using namespace std;
int main()
{
    stack stk; 
	int n, r = 0, m;
	cin >> n;
	stk.push(n);
	while(stk.empty() == false)
    {
        m = stk.top();//出栈
        stk.pop();
        if(m == 2 || m == 1)//如果遇到第二项或第一项，直接把值加到结果res中
            r += 1;
        else
        {//把后两项入栈
            stk.push(m-1);
            stk.push(m-2);
        }
    }
    cout << r;
    return 0;
}

用以上两段代码提交【OpenJudge NOI 1.5 17:菲波那契数列】会超时。该算法时间复杂度过高了，输入40时，基本要1秒后才能得到结果。

在递归算法的基础上增加记忆状态：a[i]表示斐波那契数列的第i项
在递归时，如果要求斐波那契数列第i项，先看这一项是否已经求出来过。如果已经求出过，那么直接取值。在求出一项后，将其存入记忆状态数组中。
时间内复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( n ) O(n) O(n)

#include
using namespace std;
int a[50];//a[i]:斐波那契数列第i项 
int fib(int k)//求斐波那契数列第k项 
{
	if(a[k] > 0)
		return a[k];
	else
		return a[k] = fib(k-1) + fib(k-2);
}
int main()
{
	int k;
	cin >> k;
	a[1] = a[2] = 1;
	cout << fib(k);
	return 0;
}

当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。
尾递归调用结束，上一次调用也就结束了，所以没有必要存储上一次调用中用到的临时变量。现代编译器都会针对这一特性对尾递归进行优化，减少算法的空间复杂度。
用g++编译时，加上-O2选项，即可开启尾递归优化。
时间内复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( 1 ) O(1) O(1)

#include
using namespace std;
int fib(int n1, int n2, int k)//倒数第1项是n1，倒数第2项是n2，计算k-1次 
{
    if(k == 1)
        return n2;
    else
        return fib(n1+n2, n1, k-1);
}
int main()
{
	int k;
	cin >> k;
	cout << fib(1, 1, k);
	return 0;
}

已知求斐波那契数列的通项公式 F n = ( 1 + 5 2 ) n − ( 1 − 5 2 ) n 5 F_n = frac{(frac{1+sqrt{5}}{2})^n-(frac{1-sqrt{5}}{2})^n}{sqrt{5}} Fn​=5 ​(21+5 ​​)n−(21−5 ​​)n​
输入n，代入公式，即可求值
时间内复杂度： O ( 1 ) O(1) O(1)，空间复杂度： O ( 1 ) O(1) O(1)

#include
using namespace std;
int main()
{
	int n;
	cin >> n;
	cout << int((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
	return 0;
}