#11745: C++執行逾時版


4105056029 (beginner)

學校 : 國立中興大學
編號 : 60535
來源 : [61.216.33.220]
最後登入時間 :
2017-02-17 20:30:25
a021. 大數運算 | From: [101.8.3.234] | 發表日期 : 2017-02-14 13:15

解法如下 是最土法煉鋼版的
尤其除法一定會執行逾時
敢問哪種方法可以加快除法的時間?

#include<iostream>
using namespace std;

void add(int[],int[],int[]);
void sub(int[],int[],int[]);
void mul(int[],int[],int[]);
void div(int[],int[]);
void print( int[]);

int main()
{
int c=0;
while(c<4)
{
c++;
char num1[53]={'\0'};
char num2[53]={'\0'};

int A[53]={0};
int B[53]={0};
int C[53]={0};

int digit1=0;
int digit2=0;

char op1,op2;

cin >> num1 >> op1 >> num2;

for( int i=0; i<sizeof(num1); i++)
{
if( num1[i]!='\0')
digit1++;
if( num2[i]!='\0')
digit2++;
}
for( int i=digit1; i>0; i--)
{
A[digit1-i] = num1[i-1]-'0';
}
for( int i=digit2; i>0;i--)
{
B[digit2-i] = num2[i-1]-'0';
}

if( op1=='+')
{
add(A,B,C);
print(C);
cout << endl;
}
else if( op1=='-')
{
sub(A,B,C);
print(C);
cout << endl;
}
else if( op1=='*')
{
mul(A,B,C);
print(C);
cout << endl;
}
else if( op1=='/')
{
div(A,B);
cout << endl;
}
}
return 0;
}
void add( int a[53], int b[53], int c[53])
{
for( int i=0; i<53; i++)
c[i] = a[i]+b[i];
for( int i=0; i<53; i++)
{
c[i+1] += c[i]/10;
c[i] %= 10;
}
}
void sub( int a[53], int b[53], int c[53])
{
for( int i=0; i<53; i++)
c[i] = a[i]-b[i];
for( int i=0; i<53; i++)
{
if( c[i]<0)
{
c[i] +=10;
c[i+1]-=1;
}
}
}
void mul(int a[53],int b[53],int c[53])
{
for( int i=0; i<53; i++)
{
for( int j=0; j<53; j++)
{
c[i+j] += a[i]*b[j];
}
}

for( int i=0;i<53;i++)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
void div(int a[53],int b[53])
{
int digit1,outpoint1=0,zero=1,c[53]={0};
while(zero!=0)
{
zero=0;
for(int i=0;i<53;i++)
{
zero+=a[i];
}
digit1=53;
for(int i=53-1; i>0; i--)
{
if( a[i]==0)
digit1--;
else
break;
}
for( int i=0; i<53; i++)
a[i]-=b[i];
for( int i=0; i<53; i++)
{
if( a[digit1]<0)
outpoint1=1;
if( a[i]<0)
{
a[i]+=10;
a[i+1]--;
}
}
if( outpoint1==1)
break;
c[0]++;

for(int i=0;i<53;i++)
{
if(c[i]==10)
{
c[i]-=10;
c[i+1]++;
}
}
}

int digit3=53;
for(int i=52;i>=0;i--)
{
if(c[i]==0)
digit3--;
else
break;
}
for(int i=digit3;i>0;i--)
{
cout << c[i-1];
}
}
void print(int c[53])
{


int i=53-1;

while( i>=0&& c[i]==0)
i--;

while( i>=0)
{
cout << c[i];
i--;
}
}
 
ZeroJudge Forum