斐波那契数列

  • 题目描述:

斐波那契数列以如下递归的方式定义:
$$
F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n>=2,n∈N^*)
$$
这个数列从第三项开始,每一项都等于前两项之和。

  • 解题思路:

该数列有一定的规律性,可以利用递归或者迭代方式求解。
递归调用时会有大量重复计算量,如果测试数据特别大的话,可能会造成溢出,也可以用动态规划思想来求解。

  • 源代码:

递归

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int Fibonacci(int n) {
if (n==0)
return 0;
if (n==1)
return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
};

举例:
当n=5时,通过一次次的递归调用,
Fibonacci(5)=Fibonacci(4)+Fibonacci(3)
=Fibonacci(3)+Fibonacci(2)+Fibonacci(2)+Fibonacci(1)
=Fibonacci(2)+Fibonacci(1)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)
=Fibonacci(1)+Fibonacci(0)+Fibonacci(1)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)+Fibonacci(0)+Fibonacci(1)
递归时需要将有用数据压入栈中,从递归式可以看出,当n特别大时,容易造成栈溢出。由于递归的时候,我们并不会记录Fibonacci(1)和Fibonacci(0)的结果,这样也会造成大量的重复计算,所以该方法不可取。

尾递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int Fibonacci(int n) {
return Fibonacci_tail(n,0,1);
}
int Fibonacci_tail(int n,int f1,int f2) {
if (n==0) return 0;
if (n==1) return f2;
return Fibonacci_tail(n-1,f2,f1+f2);
}
};

尾递归就是从最后开始计算,每递归一次就算出相应的结果,函数调用出现在调用者函数的尾部。因为是尾部,所以没有必要去保存任何局部变量。它是针对传统递归算法的一种优化。与方法1的递归式相比,尾递归只保留后一个函数堆栈,大大减少了栈空间的使用,也能够有效得避免了方法1会出现的栈溢出情况。

举例:
当n=5时,Fibonacci_tail(5)=Fibonacci_tail(4,1,1)=Fibonacci_tail(3,1,2)=Fibonacci_tail(2,2,3)=Fibonacci_tail(1,3,5)=5

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int Fibonacci(int n) {
if (n==0) return 0;
if (n==1) return 1;
int f1=0,f2=1;
int f3;
for (int i=2;i<=n;i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
};

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int Fibonacci(int n) {
if (n==0) return 0;
if (n==1) return 1;
int record[n+1];
for (int i=0;i<=n;i++) {
record[i] = 0;
}
record[1] = 1;
for (int i=2;i<=n;i++) {
record[i] = record[i-1]+record[i-2]; //递归关系,自底向上进行计算
}
return record[n];
}
};

想要利用动态规划去求解问题时,需要满足最优子结构性质和递归关系。根据前面对于递归解法的分析,由于斐波那契数列每一项的值都是固定不变的,可以认为满足最优子结构性质,该数列本身就有很强的递归关系,所以可以运用动态规划方式去求解。自底向上求解并保存在数组中直至找到待求解。

举例:
当n=5时,
record[2]=record[1]+record[0]=1;
record[3]=record[n2]+record[1]=2;
record[4]=record[3]+record[2]=3;
record[5]=record[4]+record[3]=5;
可以看出整个的求解过程中,并没有重复计算,每次求解时需要用到的值都已经被放进了数组中,可以直接使用。

-------------The End-------------