【君义精讲】多种方法求斐波那契数列-创新互联

概念

斐波那契数列（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:菲波那契数列

1. 迭代法

• 设置变量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)

#includeusing 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;
}

2. 递推法

• 递推状态：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)

#includeusing 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;
}

3. 递归法（一般）

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

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

#includeusing 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;
}

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

#includeusing namespace std;
int main()
{stackstk; 
	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秒后才能得到结果。

4. 记忆化递归法

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

#includeusing 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;
}

5. 尾递归法

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

#includeusing 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;
}

6. 公式法

已知求斐波那契数列的通项公式 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)

#includeusing 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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：【君义精讲】多种方法求斐波那契数列-创新互联
文章来源：http://jkwzsj.com/article/dceedj.html