可用分押宝游戏火热进行中...	专题改版：Java Web 专题

求Fibonacci 数列

楼主superbence（弘心）2004-05-03 07:35:21 在 C/C++ / C++ 语言提问

本人初学vc++，刚刚自己在程序上编写了一个简单的Fibonacci数列。即f[1]=1；
f[2]=1；f[n]=f[n-1]+f[n-2]。输入一个n，得到f[n]的值。本人的程序是没有错，比如输入一个6，得到f[6]=8。但后来突发奇想，输入一个40，那程序的输出就溢出了，用double类型都没用，还是要溢出，请问各位大狭，有没有解决此类的好技巧，即可得到正确的结果，但又不会使数据溢出。本人想的话，是不是在输出的时候有技巧啊！问题点数：20、回复次数：12Top

1 楼tianyxy（天涯夕阳）回复于 2004-05-03 10:36:46 得分 5

程序和运行结果如下：vc++6.0下调试通过
///Fibonacci数列

#include<iostream>
using namespace std;

int f(int n)
{
if(n<0)
return 0;
else
if(n==1 || n==2)
return 1;
else
return(f(n-2)+f(n-1));
}

void main()
{
int i;
do
{
cout<<"enter a number:"<<endl;
cin>>i;
cout<<"Fibonacci数列:f("<<i<<")="<<f(i)<<endl;
}while(i>0);

}

enter a number:
10
Fibonacci数列:f(10)=55
enter a number:
40
Fibonacci数列:f(40)=102334155
enter a number:

Top

2 楼tianyxy（天涯夕阳）回复于 2004-05-03 10:47:17 得分 0

就是速度很慢我的机子p4可是也要等上8-10秒Top

3 楼cngdzhang（）回复于 2004-05-03 11:54:15 得分 5

下面是一个非递归的,速度很快

#include <stdio.h>

long f(int n)
{
long n1=1,n2=1,t=1;
int i;
for(i=2;i<n;i++)
{
t=n1+n2;
n1=n2;
n2=t;
}
return t;
}

void main()
{
int n;
printf("Please Enter a number :");
scanf("%d",&n);
printf("%ld\n",f(n));
}

输入40的结果是102334155Top

4 楼antijpn（antijpn）回复于 2004-05-03 13:08:07 得分 0

40也不至于溢出吧？除非你是16bit环境里面Top

5 楼zxs790501（沧海一粟）回复于 2004-05-03 13:58:39 得分 0

用递归调用能实现的程序都可以用非递归的方法实现。
递归太慢了，每循环一次都要把函数表（函数名，函数返回类型，函数参数列表）压栈，太耗内存了。
不过它的优点很明显：编程容易（写起来容易，看起来也容易）！Top

6 楼02051223（chenlei）回复于 2004-05-03 15:11:21 得分 0

Reasonable!Top

7 楼02051223（chenlei）回复于 2004-05-03 15:17:21 得分 0

建议在main的‘}’加一句 getch（）；以免两次 ctrl+f9 看结果！Top

8 楼qyet（少年心气）回复于 2004-05-03 17:23:38 得分 0

用递归当然会很慢
Fibonacci函数中的每一层递归调用数有加倍的效果，即第n个Fibonacci书在第2^n次递归调用中计算。
第40个要2^40 次调用~~
呵呵......Top

9 楼superbence（弘心）回复于 2004-05-03 19:37:00 得分 0

真是不好意思，早上发消息的时候，忘了说明一点，40并不是我遇到的问题。这个问题单纯的用递归之类的算法，我想学过程序的都会。写的时候，只是随便写了个数字，那像你们这样利用long,或者double类型的话，那我给你们一个100，求f[100]。那我想你们的程序多半是要溢出了吧！不信试试你们的程序。其实这个问题，我考虑的应该不是用常规的算法，应该有别的技巧！问题的关键不在Fibonacci数列的传统算法上。不知道哪位高人有自己的好见解！多谢赐教！！！Top

10 楼superbence（弘心）回复于 2004-05-03 19:44:17 得分 0

f[100]=354224848179261915075。如果你们用暴力求解的话，那我想要求f[1000]，怎么办^_^
Top

11 楼Darkay_Lee（）回复于 2004-05-03 20:06:52 得分 0

算法都是一样的，如果计算机的整数类型表示不下，那么配合“大数算法”总是可以实现的拉！Top

12 楼cngdzhang（）回复于 2004-05-03 20:11:48 得分 10

那么这个就要用高精度数算法了

前几天有一个贴子有这个算法,我拷下来了,但是没有来得及验证

作者我忘了,不好意思,请作者给我发消息,下次一定把您的大名注上的

那么我的Fibonacci算法只用了加法部分,替换一下就好了

#include <iostream>
#include <string>
using namespace std;

void clear(string &s)
{
if(""==s)
s="0";
while(s.length()>0&&'0'==s[0])
{
s.erase(0,1);
}
if(""==s)
s="0";
}

bool bigger(string s1,string s2)
{
if(s1.length()>s2.length())
return true;
else
{
if(s1.length()==s2.length() && s1>=s2)
{
return true;
}
else
return false;
}
}

string add(string s1,string s2)
{
int i;
while(s1.length()<s2.length())
s1="0"+s1;
while(s1.length()>s2.length())
s2="0"+s2;
s1="0"+s1;
s2="0"+s2;
for(i=s1.length()-1;i>=0;i--)
{
s1[i]=s1[i]+s2[i]-'0';
if(s1[i]>'9')
{
s1[i]=s1[i]-10;
s1[i-1]+=1;
}
}
clear(s1);
return s1;
}

string sub(string s1,string s2)
{
int i;
while(s1.length()<s2.length())
s1="0"+s1;
while(s1.length()>s2.length())
s2="0"+s2;
for(i=s1.length()-1;i>=0;i--)
{
if(s1[i]>=s2[i])
{
s1[i]=s1[i]-(s2[i]-'0');
}
else
{
s1[i]=s1[i]+10;
s1[i-1]=s1[i-1]-1;
s1[i]=s1[i]-(s2[i]-'0');
}
}
clear(s1);
return s1;
}

string multi(string s1,string s2)
{
int i;
char c='1';
string r;
r="0";
for(i=s2.length()-1;i>=0;i--)
{
c='1';
while(c<=s2[i]){
r=add(r,s1);
c++;
}
s1=s1+"0";
}
clear(r);
return r;
}

string div(string s1,string s2)
{
int i;
string s,r;
r="";
s="";
for(i=0;i<s1.length();i++)
{
s=s+s1[i];
r=r+"0";
while(bigger(s,s2))
{
r[r.length()-1]++;
s=sub(s,s2);
}
}
clear(r);
return r;
}

int main()
{
int i;
string result[10001];
result[1]="2";
for(i=2;i<=1001;i++)
{
result[i]=multi(result[i-1],"2");
}
cout<<result[5]<<endl;
return 0;
}Top