Question

C语言。。电脑运行结果正确。。提交OJ 出现wrong answer！

Problem Description
1202年，意大利数学家斐波那契出版了他的《算盘全书》，在书中第一次提到了著名的Fibonacci数列。
现在你的任务是求出Fibonacci数列的第n项。
Input
输入数据由多组数据组成。每组数据一行，仅一个整数，表示n的值。
Output
对于每组数据，输出仅一行，即Fibonacci数列的第n项。

自己电脑运行 结果符合数列。
但是提交到OJ。。wrong answer!!!

#include<stdio.h>
void main()
{
int a,b,i,s,n;
while(scanf("%d",&n)!=EOF)
{
if(n==2||n==1)
{
s=1;
printf("%d\n",s);
}
else
{
a=s=1;
b=1;
for(i=3;i<=n;i++)
{
a=s;
s=a+b;
b=a;
}
printf("%d\n",s);
}
}
}

Answer 1

你说出来的题目不是很全，我觉得这道题是一道大数相加的题目。。。
你自己好好看看题中的N的范围是多大。当N大的一定数的时候就会超出int 或者__int64的范围。。
给你一个我以前写的斐波那契大数相加。。
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1715
参考下，自己在写写。。
#include<stdio.h>
short int fb[1001][100];
short int b[1001]={1,1,1};
int i;
void add(short int x[],short int y[],short int z[])
{
int j;
for(j=1;j<=b[i-1];j++)
x[j]=0;
for(j=1;j<=b[i-1];j++)
x[j]+=y[j];
for(j=1;j<=b[i-2];j++)
x[j]+=z[j];
for(j=1;j<b[i-1];j++)
if(x[j]>=10000)
{
x[j+1]+=(x[j]/10000);
x[j]%=10000;
}
b[i]=b[i-1];
if(x[j]>=10000)
{
b[i]++;
x[j+1]=x[j]/10000;
x[j]%=10000;
}
}
int main()
{
int t,n,j;
fb[1][1]=1;fb[2][1]=1;
for(i=3;i<=1000;i++)
add(fb[i],fb[i-1],fb[i-2]);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%hd",fb[n][b[n]]);
for(j=b[n]-1;j>0;j--)
printf("%04hd",fb[n][j]);
printf("\n");
}

return 0;
}
再给你写一个不是大数的fib。。
#include<stdio.h>
#define MAX 40 //改下范围就行了。
int main()
{
int i,j,n;
int f[MAX+1]={1,1,1}; // 也可能是__int64
for(i=3;i<=MAX;i++)
f[i]=f[i-1]+f[i-2];
while(scanf("%d",&n)!=EOF)
printf("%d\n",f[n]); //__int64 这里要改。。
return 0;
}

Answer 2

这个算法的时间复杂度比较高啊，OJ上面有提示用F(n) = F(n/2)……，自己计算一下，用那个迭代关系做。
这个迭代的有点错误，应该改成这样
a=s=1;
b=1;
for(i=3;i<=n;i++)
{
b = a; //这个应该在最前面
a =s;
s+=b;
}

Answer 3

友情帮顶了，你去找个费波拉契的函数看看，有写好的。