Question

C语言中斐波拉契数列算法

#include<stdio.h>
long int f(long int x)
{
if(x==1)
return 1;
if(x==2)
return 1;
else
return f(x-1)+f(x-2);
}

int main()
{
int a,i;
scanf("%d",&a);
for(i=1;i<a;i++)
{
printf("%d,",f(i));
}
if(i=a)
printf("%d\n",f(i));
system("pause");
return 0;
}
按照我编的这个程序，运行的时候得到前十个数很容易，可是越往后面越慢，得出第20个数到第二十一个数已经需要很长时间（我的电脑还不错的说），我认为是因为···举个例子：计算F（100），它会计算F(99)+F(98),然而F(99)它又会计算F(98)+F(97)，这样总共就要计算2^100次，所以时间很长很长。
现在我不想使用其他的函数，有什么方法可以改进的呢？是不是有某种方法能够使我得到的F(1)，F(2),F(3)分一块内存存下来，要用到的时候可以直接读取而不是再三的计算得到呢？
static long int f(long int x) 这种定义不可以实现⊙﹏⊙b。真心求助各位大牛，怎么提高运算速度。

Answer 1

你每次计算f（i）都是从头开始的（每次都从f（1）开始一步一步的算），你在循环里调用f函数也就是说对每个i函数f都从i递归到1，做了很多重复功，这就很耗费时间，大大的浪费时间空间资源。其实完全可以不用函数的，i从1开始没计算一个值就保存并输出那个，这样就只需要一次循环，很简单的。还有long int型的有效位数是10位，就算是unsigned long int型的也是只能表示从0到4294967295，更本不可能到f（100），f（100）远超出long int 可表示的范围，long int只能到第46个（1836311903）。
下面是我写的程序，你可以看看（我保留你的f函数，不过没什么用）：
#include<stdio.h>
int f(int x)
{
if(x==1)
return 1;
if(x==2)
return 1;
}

int main()
{
int a,i;
unsigned long num[101];
scanf("%d",&a);
for(i=1;i<=a;i++)
{
if(i==1||i==2)
{
num[i]=f(i);
printf("%d\n,",num[i]);
}
else
{
num[i]=num[i-1]+num[i-2];
printf("%ld\n",num[i]);
}
}

return 0;
}

Answer 2

递归 运算到后面计算量太大了
这个用递推的好！
#include <stdio.h>
void fa(int n){
int i,x=1,y=1;
for(i=1;i<=n;i++){
if(i<3)
printf("1\t");
else{
y=x+y;printf("%d\t",y);
x=y-x;
}
}
}
void main()
{
int n;
printf("input a number:\n");
scanf("%d",&n);
fa(n);
printf("\n");
system("pause");
}

Answer 3

若只是想打印结果，可以这样写：
#include<stdio.h>
long int f(long int x)
{
if(x==1)
｛printf("%d",1);
return 1;｝
if(x==2)
｛ printf("%d",1);
return 1;｝
else
{int m=f(x-1)+f(x-2);
printf("%d",m);
return m;｝
}

int main()
{
int a,i;
scanf("%d",&a);
f(a);
system("pause");
return 0;
}

追问

好多语法报错了额·····我不知道怎么改了····
是不是有某种方法能够使我得到的F(1)，F(2),F(3)分一块内存存下来，要用到的时候可以直接读取而不是再三的计算得到呢？
非常想知道这个问题有没有解决方法

追答

把int 声明改 为long int 看看。
可以记录f(N)的数值。需要修改一下函数

f(int n,int *a)//a为长度>=N的动态数组，传入f当参数时，须初始化每一行为0，完成程序后，a中就保存了对应的数值。
{
if(a[n]!=0)
{ return a[n] ;}
else if(n==1||n==2)
{ a[n]=1;
return 1;}
else
{a[n]= f(n-1,a)+f(n-2,a);
return a[n] ;}
}

}

Answer 4

main()

　　{

　　long fib[40] = {1,1};

　　int i;

　　for(i=2;i<40;i++)

　　{

　　fib[i ] = fib[i-1]+fib[i-2];

　　}

　　for(i=0;i<40;i++)

　　{

　　printf("F%d==%d\n", i, fib[ i]);

　　}

　　return 0;

　　}

追问

输出的结果完全不对啊······⊙﹏⊙b汗

追答

//利用循环输出前40项
　　#include
　　int main()
　　{
　　long fib[41] = {0,1};
　　int i;
　　for(i=2;i1) return fib(n-1)+fib(n-2);
　　}
　　int main()
　　{
　　int k=1;
　　while(k!=0)
　　{
　　puts("input a num n 0 for exit");
　　scanf("%d",&k);
　　printf("%ld\n",fib(k));
　　}
　　getch();
　　return 0;
　　}
　　//高精度斐波那契数列（3000长度的可求到第10000多项）
　　#include
　　#include
　　using namespace std;
　　int a[3001]={};
　　int b[3001]={};
　　int c[3001]={};
　　int n;
　　int main()
　　{
　　scanf("%d",&n);
　　if(n=10)
　　{c[j]=c[j]-10;
　　c[j+1]=1;}
　　}
　　}
　　int i=3000;
　　while(c[i]==0) i--;
　　for(i=i;i>=1;i--)
　　printf("%d",c[i]);
　　printf("\n");
　　system("pause");
　　return 0;
　　}

Answer 5

haha