c++大数加減乗除(高精度演算の加算、減算、乗算、除法)
でたらめシリーズ
いつ先生が教えてくれたか忘れてしまった大数加減乗除も、久しぶりにcやc++に触ったことがありません.面接問題をブラシしたとき、多くのプログラミング問題が最初から大数に及ぶことに気づきました.
なぜ高精度を使うのか
まずcのデータ型の整数型を普及させ、基本的に理解するのは以下の通りである.
を選択します.
ストレージ・サイズ
範囲
char
1バイト
-128～127または0～255
unsigned char
1バイト
0～255
signed char
1バイト
-128～127
int
4バイト
-21147483648～2147483647
unsigned int
4バイト
0～4294967295
short
2バイト
-32768～32767
unsigned short
2バイト
0～65535
long
4バイト
-21147483648～2147483647
unsigned long
4バイト
0～4294967295
整数演算を行う場合、コンピュータは-2114748648から2147483647の範囲の整数しか演算できません.データオーバーフローによるコンピュータ演算エラーを防止するために、コンピュータの演算の代わりに何らかの方法を使用します.
高精度演算の減算
テストデータ
高精度演算の加算
テストデータ4444444444444444444444444444 6555555555555555555555555結果10999999999999999999999999999999
高精度演算の乗算
テストデータ123456789 123456789演算結果15241578750190521
高精度演算の除算
テストデータ15241578750190521 123456789演算結果123456789
これからもずっと書き続けてほしい.
いつ先生が教えてくれたか忘れてしまった大数加減乗除も、久しぶりにcやc++に触ったことがありません.面接問題をブラシしたとき、多くのプログラミング問題が最初から大数に及ぶことに気づきました.
なぜ高精度を使うのか
まずcのデータ型の整数型を普及させ、基本的に理解するのは以下の通りである.
を選択します.
ストレージ・サイズ
範囲
char
1バイト
-128～127または0～255
unsigned char
1バイト
0～255
signed char
1バイト
-128～127
int
4バイト
-21147483648～2147483647
unsigned int
4バイト
0～4294967295
short
2バイト
-32768～32767
unsigned short
2バイト
0～65535
long
4バイト
-21147483648～2147483647
unsigned long
4バイト
0～4294967295
整数演算を行う場合、コンピュータは-2114748648から2147483647の範囲の整数しか演算できません.データオーバーフローによるコンピュータ演算エラーを防止するために、コンピュータの演算の代わりに何らかの方法を使用します.
高精度演算の減算
#include
#include
#define MAX 100001
using namespace std;
int subtraction(char a[],char b[],int c[]){
int len1,len2,i,j,k;
k=0;
len1=strlen(a)-1;
len2=strlen(b)-1;
for(i=len1,j=len2;i>=0;i--,j--)
{
if(j>=0)//
{
if(a[i]=0;i--)
if(c[i]!=0)
break;
return i;
}
int main(void)
{
char a[MAX],b[MAX];
int c[MAX];
int len;
while(scanf("%s%s",a,b)!=EOF)
{
len=subtraction(a,b,c);
// 0
if(len>=0)
for(;len>=0;len--)
printf("%d",c[len]);
else
printf("0");
printf("
");
}
return 0;
}
テストデータ
高精度演算の加算
#include
#include
#define MAX 100001
using namespace std;
int addition(char a[],char b[],int c[]){
int len1,len2,i,j,k,sign;
sign=0;k=0;
len1=strlen(a)-1;
len2=strlen(b)-1;
for(i=len1,j=len2;i>=0||j>=0;i--,j--)
{
if(j>=0&&i>=0)
{
if(a[i]+b[j]+sign>'0'+'0'+9)
{
c[k]=a[i]+b[j]-'0'-'0'-10+sign;
sign=1;
}
else
{
c[k]=a[i]+b[j]-'0'-'0'+sign;
sign=0;
}
}
else if(i>=0&&j<0)
{
if(a[i]+sign>'9')
{
c[k]=0;
}
else
{
c[k]=a[i]-'0'+sign;
sign=0;
}
}
else
{
if(b[j]>='9'&&sign==1) c[k]=0;
else
{
c[k]=b[j]-'0';
sign=0;
}
}
k++;
}
if(sign==1)
{
c[k]=1;
k++;
}
for(i=k-1;i>=0;i--)
if(c[i]!=0)
break;
return i;
}
int main(void)
{
char a[MAX],b[MAX];
int c[MAX];
int len;
while(scanf("%s%s",a,b)!=EOF)
{
len=addition(a,b,c);
// 0
if(len>=0)
for(;len>=0;len--)
printf("%d",c[len]);
else
printf("0");
printf("
");
}
return 0;
}
テストデータ4444444444444444444444444444 6555555555555555555555555結果10999999999999999999999999999999
高精度演算の乗算
#include
#include
using namespace std;
typedef string BigInt;
BigInt ClearZero(BigInt x) // 0
{
int i;
for (i = 0; i < x.length(); i++)
if (x[i] != '0')
break;
if (i == x.length())
return "0";
else
return x.erase(0, i);
}
BigInt addition(BigInt a, BigInt b)
{
int l1 = a.length();
int l2 = b.length();
while (l1 < l2) // ， 0
{
a = '0' + a;
l1++;
}
while (l1 > l2)
{
b = '0' + b;
l2++;
}
a='0'+a;
b='0'+b;
// cout<= 0; i--)
{
if (( a[i] + b[i] )>( '0' + 9 +'0' ))
{
a[i] -= 10;
a[i-1]++;
}
a[i]=a[i]+b[i] - '0';
// cout << a[i] << endl;
}
return ClearZero(a);
}
BigInt multiplication(BigInt a,BigInt b)
{
BigInt c="0",d;
int i,j;
for(j=b.length()-1 ;j>=0;j--)
{
d=a;
for(i=2;i<=(b[j]-'0');i++)
d=addition(d,a);
if((b[j]-'0')>0)c=addition(c,d);
a=a+'0';
}
return c;
}
int main()
{
BigInt a, b;
while (cin>>a>>b)
{
cout< テストデータ123456789 123456789演算結果15241578750190521
高精度演算の除算
#include
#include
#define MAX 100001
using namespace std;
int SubStract(int *p1, int len1, int *p2, int len2)
{
int i;
if(len1 < len2)
return -1;
if(len1 == len2 )
{ // p1 > p2
for(i = len1-1; i >= 0; i--)
{
if(p1[i] > p2[i]) // ， ，
break;
else if(p1[i] < p2[i]) // -1
return -1;
}
}
for(i = 0; i <= len1-1; i++) //
{
p1[i] -= p2[i]; //
if(p1[i] < 0) //
{ //
p1[i] += 10;
p1[i+1]--;
}
}
for(i = len1-1; i >= 0; i--) //
{
if( p1[i] ) // 0
return (i+1); //
}
return 0; // 0
}
int Division(char num1[], char num2[], int sum[])
{
int k, i, j;
int len1, len2, len=0; //
int dValue; //
int nTemp; //Subtract
int num_a[MAX] = {0}; //
int num_b[MAX] = {0}; //
int num_c[MAX] = {0}; //
len1 = strlen(num1); //
len2 = strlen(num2);
// ，
for( j = 0, i = len1-1; i >= 0; j++, i-- )
num_a[j] = num1[i] - '0';
for( j = 0, i = len2-1; i >= 0; j++, i-- )
num_b[j] = num2[i] - '0';
if( len1 < len2 ) // ， -1， 0
{
return -1;
}
dValue = len1 - len2; //
for (i = len1-1; i >= 0; i--) // ，
{
if (i >= dValue)
num_b[i] = num_b[i-dValue];
else // 0
num_b[i] = 0;
}
len2 = len1;
for(j = 0; j <= dValue; j++ ) // ， ，
{
while((nTemp = SubStract(num_a, len1, num_b+j, len2-j)) >= 0)
{
len1 = nTemp; //
num_c[dValue-j]++; // ， 1
}
}
// ， sum
for(i = MAX-1; num_c[i] == 0 && i >= 0; i-- ); // 0，
if(i >= 0)
len = i + 1; //
for(j = 0; i >= 0; i--, j++) // sum
sum[j] = num_c[i];
return len; //
}
int main(void)
{
char a[MAX],b[MAX];
int c[MAX];
int len;
while(scanf("%s%s",a,b)!=EOF)
{
len=Division(a,b,c);
// 0
if(len>=0)
for(int i = 0; i < len; i++ )
printf("%d",c[i]);
else
printf("0");
printf("
");
}
return 0;
}
テストデータ15241578750190521 123456789演算結果123456789
これからもずっと書き続けてほしい.