用递归和迭代分别处理斐波那契数列

用递归和迭代分别处理斐波那契数列

/*************************************************基础求法：*************************************************/int Fib(int i){ int a=1,b=1,j,sum=0; if (i==0) return 0; else if(i==1) return 1; else { for(j=2;j<=i;j++) { sum=a+b; a=b; b=sum; } return sum; }****************************#includeusing namespace std;int fact(int n)//阶乘递归求法{ if (n==0) return 1; return n*fact(n-1);}************************** int fib(int n)//递归求法{ if(n<=1) return n; return fib(n-1)+fib(n-2);}int main ( ){ int a, b; while(cin>>a) { cout<

这两种办法在文章部分已经都有提及，基本思想都是大数相加，一种是字符串相加，一种是数组保存位数

第一种，字符串相加

直接用一个字符串相加函数，计算结果保存到字符串数组中

代码：

string operator +(const string s1,const string s2){ string s; int l1=s1.size(),l2=s2.size(),i,j; int a[1100]={0},k=0; for(i=l1-1,j=l2-1;i>=0||j>=0;i--,j--,k++) { if(i>=0) a[k]+=(s1[i]-'0'); if(j>=0) a[k]+=(s2[j]-'0'); if(a[k]>9) { a[k+1]+=1; a[k]%=10; } } s=""; for(i=k;i>=0;i--) { if(i==k) { if(a[k]) s+=a[k]+'0'; } else s+=a[i]+'0'; } return s;} int main(){ string a,b; fib[0] = "1"; fib[1] = "1"; for(int i = 2; i < 1024; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } fib[0] = "0";}

第二种，用一个二维数组来保存，fb[n][i]表示第n个fib数的第i位数

代码：

#include #include #include #include using namespace std; int fb[6001][1003]; int main(void){ int len[6002]; int n; memset(fb,0,sizeof(fb)); fb[1][0] = 1; fb[2][0] = 1; len[1] = 1; len[2] = 1; for(int i=3; i<=6000; i++) { memcpy(fb[i],fb[i-1],sizeof(fb[i-1])); int tlen = max(len[i-1],len[i-2]); for(int k=0; k= 10 ) { fb[i][k+1]++; fb[i][k] %= 10; } if( fb[i][tlen] != 0 ) tlen++; len[i] = tlen; } while( cin >> n ) { for(int i=len[n]-1; i>=0; i--) cout << fb[n][i]; cout << endl; } return 0;}

这是一个很经典的C语言编程题，但是很多人却用递归处理，不能不说是一大悲剧！递归的效率如此之低，代价如此之大，真是得不偿失。迭代可以有效低解决这个问题，代价小，效率高。

两种方式的代码如下：

#include#includelong Fibonacci_iteration(int n);long Fibonacci_recursion(int n);long main(void) {   int n = 0;  clock_t start = 0, finish = 0;  printf("求第n个斐波那契数,n = ");  scanf("%d",&n);  start = clock();  printf("迭代:第%d个斐波那契数为:%d\n",n,Fibonacci_iteration(n));  printf("耗时:%d\n\n\n",clock() - start);  start = clock();  printf("递归:第%d个斐波那契数为:%d\n",n,Fibonacci_recursion(n));  printf("耗时:%d\n",clock() - start);  return 0; }long Fibonacci_iteration(int n){  long result = 1;  long num_provious = 1;  long num_next = 1;  while(n-- > 2)  {    result = num_provious + num_next;    num_provious = num_next;    num_next = result;  }  return result;}long Fibonacci_recursion(int n){  if (n <=2)  {    return 1;  }  return Fibonacci_recursion(n-1)+Fibonacci_recursion(n-2);}
执行结果：
我只求第40个斐波那契数，通过耗时可以明显对比两种方法的效率！当然再大点，数据将会溢出，但即使溢出，迭代也会很快结束运算，而递归运气好的话等三五分钟，运气差的话直接栈溢出，程序结束！
/*************************************************基础求法：*************************************************/int Fib(int i){        int a=1,b=1,j,sum=0;    if (i==0) return 0;    else if(i==1) return 1;    else    {        for(j=2;j<=i;j++)        {            sum=a+b;            a=b;            b=sum;        }        return sum;    }****************************#includeusing namespace std;int fact(int n)//阶乘递归求法{    if (n==0) return 1;    return n*fact(n-1);}************************** int fib(int n)//递归求法{    if(n<=1) return n;    return fib(n-1)+fib(n-2);}int main ( ){    int a, b;    while(cin>>a)    {        cout<
这两种办法在文章部分已经都有提及，基本思想都是大数相加，一种是字符串相加，一种是数组保存位数
第一种，字符串相加
直接用一个字符串相加函数，计算结果保存到字符串数组中
代码：
string operator +(const string s1,const string s2){    string s;    int l1=s1.size(),l2=s2.size(),i,j;    int a[1100]={0},k=0;    for(i=l1-1,j=l2-1;i>=0||j>=0;i--,j--,k++)    {        if(i>=0)            a[k]+=(s1[i]-'0');        if(j>=0)            a[k]+=(s2[j]-'0');        if(a[k]>9)        {            a[k+1]+=1;            a[k]%=10;        }    }    s="";    for(i=k;i>=0;i--)    {        if(i==k)        {            if(a[k])                s+=a[k]+'0';        }        else s+=a[i]+'0';    }   return s;} int main(){      string a,b;      fib[0] = "1";      fib[1] = "1";      for(int i = 2; i < 1024; i++)      {              fib[i] = fib[i - 1] + fib[i - 2];      }          fib[0] = "0";}
第二种，用一个二维数组来保存，fb[n][i]表示第n个fib数的第i位数
代码：
#include #include #include #include  using namespace std; int fb[6001][1003]; int main(void){    int len[6002];    int n;    memset(fb,0,sizeof(fb));    fb[1][0] = 1;    fb[2][0] = 1;    len[1] = 1;    len[2] = 1;    for(int i=3; i<=6000; i++)    {        memcpy(fb[i],fb[i-1],sizeof(fb[i-1]));        int tlen = max(len[i-1],len[i-2]);        for(int k=0; k= 10 )            {                fb[i][k+1]++;                fb[i][k] %= 10;            }        if( fb[i][tlen] != 0 )            tlen++;        len[i] = tlen;    }    while( cin >> n )    {        for(int i=len[n]-1; i>=0; i--)            cout << fb[n][i];        cout << endl;    } return 0;}
这是一个很经典的C语言编程题，但是很多人却用递归处理，不能不说是一大悲剧！递归的效率如此之低，代价如此之大，真是得不偿失。迭代可以有效低解决这个问题，代价小，效率高。
两种方式的代码如下：
#include#includelong Fibonacci_iteration(int n);long Fibonacci_recursion(int n);long main(void) {   int n = 0;  clock_t start = 0, finish = 0;  printf("求第n个斐波那契数,n = ");  scanf("%d",&n);  start = clock();  printf("迭代:第%d个斐波那契数为:%d\n",n,Fibonacci_iteration(n));  printf("耗时:%d\n\n\n",clock() - start);  start = clock();  printf("递归:第%d个斐波那契数为:%d\n",n,Fibonacci_recursion(n));  printf("耗时:%d\n",clock() - start);  return 0; }long Fibonacci_iteration(int n){  long result = 1;  long num_provious = 1;  long num_next = 1;  while(n-- > 2)  {    result = num_provious + num_next;    num_provious = num_next;    num_next = result;  }  return result;}long Fibonacci_recursion(int n){  if (n <=2)  {    return 1;  }  return Fibonacci_recursion(n-1)+Fibonacci_recursion(n-2);}
执行结果：
我只求第40个斐波那契数，通过耗时可以明显对比两种方法的效率！当然再大点，数据将会溢出，但即使溢出，迭代也会很快结束运算，而递归运气好的话等三五分钟，运气差的话直接栈溢出，程序结束！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。