我写了一段代码,它使用我自己的乘法和加法任意精度函数计算斐波那契数。
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
#define max 3000
struct data_type{
int string[max];
};
struct data_type mul(struct data_type a,struct data_type b) {
struct data_type c;
memset(c.string,0,sizeof(int)*max);
int k;
int i,j;
for(i=max-1;i>0;i--) {
int num=a.string[i];
int carry=0;
int rem=0;
k=i;
for(j=max-1;j>0;j--) {
int n=b.string[j]*num + carry;
int r=n%10;
carry=n/10;
int p=(c.string[k]+r+rem)%10;
rem=(c.string[k]+r+rem)/10;
c.string[k]=p;
k--;
}
}
return c;
}
struct data_type add(struct data_type a,struct data_type b) {
struct data_type c;
memset(c.string,0,sizeof(int)*max);
int carry=0;
int i,j;
int k=max-1;
for(i=max-1,j=max-1;i>0 && j>0;i--,j--) {
int res=(a.string[i] + b.string[j])+carry;
carry=res/10;
c.string[k--]=res%10;
}
return c;
}
void multiply(struct data_type f[2][2],struct data_type m[2][2]){
struct data_type x,y,z,t;
x=add(mul(f[0][0],m[0][0]),mul(f[0][1],m[1][0]));
y=add(mul(f[0][0],m[0][1]),mul(f[0][1],m[1][1]));
z=add(mul(f[1][0],m[0][0]),mul(f[1][1],m[1][0]));
t=add(mul(f[1][0],m[0][1]),mul(f[1][1],m[1][1]));
f[0][0]=x;
f[0][1]=y;
f[1][0]=z;
f[1][1]=t;
}
void power(struct data_type f[2][2],unsigned long long n){
if((n==0)||(n==1))
return ;
struct data_type a,b;
memset(a.string,0,sizeof(int)*max);
memset(b.string,0,sizeof(int)*max);
a.string[max-1]=1;
b.string[max-1]=0;
struct data_type m[2][2]={{a,a},{a,b}};
power(f,n/2);
multiply(f,f);
if(n%2 != 0)
multiply(f,m);
}
struct data_type fib(unsigned long long n){
struct data_type a,b;
memset(a.string,0,sizeof(int)*max);
memset(b.string,0,sizeof(int)*max);
a.string[max-1]=1;
b.string[max-1]=0;
struct data_type f[2][2]={{a,a},{a,b}};
if(n==0)
return b;
power(f,n-1);
return f[0][0];
}
int main()
{
int t;
cin>>t;
for(int w=0;w<t;w++){
unsigned long long n;
cin>>n;
struct data_type a,b,c;
a=fib(n-1);
b=fib(n+2);
c=add(a,b);
int ck=0;
for(int i=0;i<max;i++) {
if(c.string[i] && !ck)
ck=1;
if(ck)
cout<<c.string[i];
}
cout<<"n";
}
return 0;
}
我的问题是,它在运行时显示SIGSEGV,但有时运行正确——例如,我在fib(50000)上测试了它的max=4000,但一旦我更改max=5000,它就会停止工作。我头疼了好几个小时,但还是没能弄清楚这个问题。
请告诉我我的代码可能出了什么问题。
代码中是否存在导致运行时错误的逻辑错误?
我认为问题出在mul()
函数中,因为内部for
循环中的索引k
可能变成负整数,而k
用于索引数组。
k
总是递减max - 1
次,但仅在外部for
循环的第一次迭代中将其设置为max - 1
。在外部for
循环的后续迭代中,它被设置为小于max - 1
的值,导致k
变为负。
编辑:
我修改了内部for
循环:
for(j=max-1;j>0;j--){
if (k < 0)
std::cout << k << "n";
...
}
并在执行过程中提示时提供CCD_ 13和CCD_。
MAX
值较大的问题可能源于在堆栈上创建大型数组,从而导致堆栈溢出。
尝试使用new
动态分配对象,并查看SIGSEGV
错误是否消失。