rambo

斐波那契（递归与尾递归讨论）

2015年9月6日 Data Strcuture 1 Comment

斐波那契数列

0、1、1、2、3、5、8、13、21、34、...

一、递归方式：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2，n∈N*）

用递归需要注意以下两点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归一般用于解决三类问题：
　  (1)数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
　  (2)问题解法按递归实现。（回溯）
　  (3)数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）
递归的缺点：
　　递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。

1
2
3
4
5
6
7
8
9
10
11
int Fibonacci1(int index){
if(index<=0){
return 0;
}
else if(index==1){
return 1;
}
else{
return Fibonacci1(index-1)+Fibonacci1(index-2);
}
}

04214621-bde3e339931444a1a56ce66dd73d1f9b

 

分析上式，在计算F(n)时，需要计算F(2)到F(n-1)每一项的值，显然存在着很多重复计算。如何减少重复计算，可以用一个数组存储所有已经计算过的项，用空间换取时间。时间复杂度为O(n)，空间复杂度也为O(n)。

尾递归方式：

函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。

尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。

1
2
3
4
5
6
7
8
int FibonacciTailRecursive(int index,int ret1,int ret2){
  if(index==0)
    return ret1;
  else if(index==1){
  return ret2;
  }
  return FibonacciTailRecursive(index-1,ret2,ret1+ret2);
}

04221026-166e3bca62d14ea7bb37eee0e6390d2d

二、数组实现    空间复杂度和时间复杂度都是0(n)，效率一般，比递归来得快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Fibonacci2(int index){
if(index<=0){
return 0;
}
else if(index==1){
return 1;
}
int *a=new int[index];
a[0]=a[1]=1;
for(int i=2;i<index;i++){
a[i]=a[i-1]+a[i-2];
}
int m=a[index-1];
delete a;
return m;
}

三、求解通项公式

F(n)=F(n-1)+F(n-2)可以得到F(n)的特征方程为x^{2}=x+1。得到x_{1,2}=\frac{1\pm \sqrt{5}}{2}

所以存在A,B使得：F(n)=A\times (\frac{1+\sqrt{5}}{2})^{n}+B\times (\frac{1-\sqrt{5}}{2})^{n}

代入F(0)=0,F(1)=1，解得A=\frac{\sqrt{5}}{5},B=-\frac{\sqrt{5}}{5}，即

F(n)=\frac{\sqrt{5}}{5}\times (\frac{1+\sqrt{5}}{2})^{n}-\frac{\sqrt{5}}{5}\times (\frac{1-\sqrt{5}}{2})^{n}

1
2
3
4
5
6
#include <cmath>
using namespace std;
int Fibonacci3(int n){
double sqrt5=sqrt((double)5);
return (pow((1+sqrt5),n)-pow((1-sqrt5),n))/(pow((double)2,n)*sqrt5);
}

由于double类型的精度还不够，所以程序算出来的结果会有误差，如果把公式展开计算，得出的结果就是正确的。

1
2
3
4
5
6
7
8
9
10
11
//二分法计算a的n次方函数
int pow(int a,int n){
int ans=1;
while(n){
if(n&1)
ans*=a;
a*=a;
n>>=1;
}
return ans;
}

四、queue<int>实现

时间复杂度是0(n)，空间复杂度是0(1)

f(n)=f(n-1)+f(n-2)，f(n)只和f(n-1)和f(n-2)有关，f(n)入队列后，f(n-2)就可以出队列了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <queue>
int Fibonacci4(int index){
if(index<=0){
return 0;
}
else if(index==1){
return 1;
}
queue<int> myqueue;
myqueue.push(1);
myqueue.push(1);
for(int i=2;i<index;i++){
myqueue.push(myqueue.front()+myqueue.back());
myqueue.pop();//保证队列中始终只有两个值
}
return myqueue.back();
}

 queue的back()和front()值得研究。

五、迭代实现
迭代实现是最高效的，时间复杂度是0(n)，空间复杂度是0(1)。

一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Fibonacci5(int index){
int i,a=1,b=1,c=1;
 
if(index<=0){
return 0;
}
else if(index==1){
return 1;
}
 
for(int i=2;i<index;i++){
c=a+b;//辗转相加法（类似于求最大公约数的辗转相除法）
a=b;
b=c;
}
return c;
}

六、分治策略

注意到Fibonacci数列是二阶递推数列，所以讯在一个2*2的矩阵，使得(x_{n} x_{n-1})=A*(x_{n-1} x_{n-2})

201305240940433

如何求解A的方幂？A^{n}=A*A*...*A。最直接的方法就是通过n-1次乘法。但当n很大时，比如10000000000，显然无法计算。

A^{x+y}=A^{x}*A^{y}

A^{x*2}=A^{x+x}=(A^{x})^{2}

用二进制表示n：n=a_{k}*2^{k}+a_{k-1}*2^{k-1}+...+a_{1}*2^{1}+a_{0}，其中a_{i}=0 or 1,i=0,1,...,k

A^{n}=A^{a_{k}*2^{k}+a_{k-1}*2^{k-1}+...+a_{1}*2^{1}+a_{0}}=(A^{2^{k}})^{a_{k}}*(A^{2^{k-1}})^{a_{k-1}}*...*(A^{2^{1}})^{a_{1}}*A^{a_{0}}

如果能够得到A^{2^{i}}(i=1,2,..,k)的值，就可以通过log_{2}{n}次乘法得到A^{n}。

递归可得A^{2^{i}}=(A^{2^{i-1}})^{2}

代码有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void multiply(int c[2][2],int a[2][2],int b[2][2],int mod)
{
int tmp[4];
tmp[0]=a[0][0]*b[0][0]+a[0][1]*b[1][0];
tmp[1]=a[0][0]*b[0][1]+a[0][1]*b[1][1];
tmp[2]=a[1][0]*b[0][0]+a[1][1]*b[1][0];
tmp[3]=a[1][0]*b[0][1]+a[1][1]*b[1][1];
c[0][0]=tmp[0]%mod;
c[0][1]=tmp[1]%mod;
c[1][0]=tmp[2]%mod;
c[1][1]=tmp[3]%mod;
}//计算矩阵乘法，c=a*b
 
int Fibonacci6(int n,int mod)//mod表示数字太大时需要模的数
{
if(n==0)return 0;
else if(n<=2)return 1;//这里表示第0项为0，第1，2项为1
int a[2][2]={{1,1},{1,0}};
int result[2][2]={{1,0},{0,1}};//初始化为单位矩阵
int s;
n-=2;
while(n>0)
{
if(n%2 == 1)
multiply(result,result,a,mod);
multiply(a,a,a,mod);
n /= 2;
}//二分法求矩阵幂
s=(result[0][0]+result[0][1])%mod;//结果
return s;
}

参考：http://www.jb51.net/article/37286.htm

 

优先队列三大利器——二项堆、斐波那契堆、Pairing 堆

http://dsqiu.iteye.com/blog/1714961