這是數(shù)據(jù)結(jié)構(gòu)老師布置的一道題：
寫一個(gè)函數(shù)計(jì)算斐波那契數(shù)列第n項(xiàng)值（n>=1)，并通過主函數(shù)調(diào)用該函數(shù)進(jìn)行測試畸冲。
n的測試范圍是整數(shù)范圍嫉髓。
剛拿到手，理所當(dāng)然的用了最常用的方法
int Fibonacci(int n)
{
int a[100];
int i;
for(i=1;i<=n;i++){
if(i==1||i==2)
a[i]=1;
else
a[i]=a[i-1]+a[i-2];
}
return a[n-1];
}
但是測試時(shí)會(huì)發(fā)現(xiàn)當(dāng)n等于47時(shí)邑闲，運(yùn)行結(jié)果便出現(xiàn)了錯(cuò)誤算行，已經(jīng)超出精度范圍。
換成了long也是只能計(jì)算到第46項(xiàng)监憎，
即使換成了double也只能計(jì)算到第102項(xiàng)纱意，
那么只能用別的方法了婶溯。
計(jì)算到后期鲸阔，相加的兩數(shù)都非常大，那么可考慮用高精度加法來計(jì)算迄委，即褐筛，將大數(shù)用數(shù)組存儲(chǔ)，再進(jìn)行計(jì)算叙身。代碼如下：
int a[1001][1001];
void Fibonacci(int n)
{
int i,j,sum=0;
memset(a,0,sizeof(a)); //初始化二維數(shù)組a
a[1][0]=1;
a[2][0]=1;
for(i=3;i<=n;i++) // i 表示第i個(gè)數(shù)
{
for(j=0;j<1001;j++)
{
sum+=a[i-1][j]+a[i-2][j];
a[i][j]=sum%10; //將大數(shù)倒著存入數(shù)組中
sum/=10;
}
}
for(i=1000;i>=0;i--) //遍歷數(shù)組渔扎，找到開始不為0的第一項(xiàng)
{
if(a[n][i])
break;
}
printf("%d",a[n][i--]); // 將大數(shù)輸出
for(j=i;j>=0;j--)
{
printf("%d",a[n][j]);
}
}
