用c++语言高精度计算写以下程序:求斐波那契数列第n项。(大整数加法)输出n,输出斐波那契数列第n项值。n<=500。
时间: 2024-03-22 20:37:09 浏览: 62
好的,以下是用C++语言实现高精度加法的代码,可以用来计算大整数:
```c++
#include<bits/stdc++.h>
using namespace std;
const int N = 10010; // 大整数的最大位数
int f[N][N], ans[N]; // f表示斐波那契数列,ans表示答案
int main()
{
int n;
cin >> n;
f[1][1] = 1, f[2][1] = 1; // 初始化斐波那契数列的前两项
for(int i = 3; i <= n; i++)
{
int len = max(strlen(f[i-1]), strlen(f[i-2])); // 计算两个数的位数的最大值
for(int j = 0; j < len; j++) // 高精度加法
{
f[i][j] += f[i-1][j] + f[i-2][j];
if(f[i][j] >= 10)
{
f[i][j+1] += f[i][j] / 10;
f[i][j] %= 10;
}
}
if(f[i][len] > 0) len++; // 最高位有进位的情况
for(int j = 0; j < len; j++) f[i][j] = f[i][j+1]; // 去掉前导零
memset(f[i-2], 0, sizeof(f[i-2])); // 释放内存
}
int len = strlen(f[n]); // 计算答案的位数
for(int i = 0; i < len; i++) ans[i] += f[n][i]; // 高精度加法
for(int i = 0; i < len; i++) // 处理进位
{
if(ans[i] >= 10)
{
ans[i+1] += ans[i] / 10;
ans[i] %= 10;
}
}
if(ans[len] > 0) len++; // 最高位有进位的情况
cout << n << endl; // 输出n
for(int i = len-1; i >= 0; i--) cout << ans[i]; // 倒序输出答案
cout << endl;
return 0;
}
```
然后我们就可以在主函数中调用这个高精度加法的代码,求出斐波那契数列的第n项了。
阅读全文