大整数計算(C++テンプレート)
6887 ワード
大整数計算(C++テンプレート)
コンピュータの記憶整数の大きさは限られており、long longは最大64ビットしか記憶できず、intは32ビットしか記憶できない.64ビットを超える整数を計算するには、別の方法が必要です.これが大整数演算です.再試験の問題にもしばしば登場する.大整数計算のテンプレートをいくつか整理しましたが、正整数の計算しかできず、減算時に小数を大きくするとエラーが発生することに注意してください.機械は何を使って計算するかを試して、中の対応するコードを叩くだけでいいです.(コードはコンピューター大学院受験-機械試験ガイドを参考にしていますが、本のコードは減算、乗算、除算を計算するのに間違いがあるので、直しました.次のコードでは間違いをマークします)ここに計算の大数加算テンプレートのテーマをあげます.
ダイレクトコード
コンピュータの記憶整数の大きさは限られており、long longは最大64ビットしか記憶できず、intは32ビットしか記憶できない.64ビットを超える整数を計算するには、別の方法が必要です.これが大整数演算です.再試験の問題にもしばしば登場する.大整数計算のテンプレートをいくつか整理しましたが、正整数の計算しかできず、減算時に小数を大きくするとエラーが発生することに注意してください.機械は何を使って計算するかを試して、中の対応するコードを叩くだけでいいです.(コードはコンピューター大学院受験-機械試験ガイドを参考にしていますが、本のコードは減算、乗算、除算を計算するのに間違いがあるので、直しました.次のコードでは間違いをマークします)ここに計算の大数加算テンプレートのテーマをあげます.
ダイレクトコード
#include
#include
#include
#include
using namespace std;
const int MAXN = 10000;
struct BigInteget
{
int digit[MAXN];
int length;
BigInteget();
BigInteget(int x);
BigInteget(string str);
BigInteget(const BigInteget& b);
BigInteget operator =(int x);
BigInteget operator =(string str);
BigInteget operator =(const BigInteget& b);
bool operator <=(const BigInteget& b);
bool operator ==(const BigInteget& b);
BigInteget operator +(const BigInteget& b);
BigInteget operator -(const BigInteget& b);
BigInteget operator *(const BigInteget& b);
BigInteget operator /(const BigInteget& b);
BigInteget operator %(const BigInteget& b);
friend istream& operator>>(istream& in, BigInteget& x);
friend ostream& operator<>(istream& in, BigInteget& x)
{
string str;
in >> str;
x = str;
return in;
}
ostream& operator<= 0; i--)
out << x.digit[i];
return out;
}
BigInteget::BigInteget()
{
memset(digit, 0, sizeof(digit));
length = 0;
}
BigInteget::BigInteget(int x)
{
memset(digit, 0, sizeof(digit));
length = 0;
if(x == 0)
digit[length++] = x;
while(x)
{
digit[length++] = x % 10;
x /= 10;
}
}
BigInteget::BigInteget(string str)
{
memset(digit, 0, sizeof(digit));
length = str.size();
for(int i = 0; i < length; i++)
digit[i] = str[length-i-1] - '0';
}
BigInteget::BigInteget(const BigInteget& b)
{
memset(digit, 0, sizeof(digit));
length = b.length;
for(int i = 0; i < length; i++)
digit[i] = b.digit[i];
}
BigInteget BigInteget::operator=(int x)
{
memset(digit, 0, sizeof(digit));
length = 0;
if(x == 0)
digit[length++] = x;
while(x)
{
digit[length++] = x % 10;
x /= 10;
}
return *this;
}
BigInteget BigInteget::operator=(string str)
{
memset(digit, 0, sizeof(digit));
length = str.size();
for(int i = 0; i < length; i++)
digit[i] = str[length-i-1] - '0';
return *this;
}
BigInteget BigInteget::operator=(const BigInteget& b)
{
memset(digit, 0, sizeof(digit));
length = b.length;
for(int i = 0; i < length; i++)
digit[i] = b.digit[i];
return *this;
}
bool BigInteget::operator<=(const BigInteget& b)
{
if(length < b.length)
return true;
else if (b.length < length)
return false;
else
{
for(int i = length -1; i >= 0; i--)
{
if(digit[i] == b.digit[i])
continue;
else
return digit[i] < b.digit[i];
}
}
return true;
}
bool BigInteget::operator==(const BigInteget& b)
{
if(length != b.length)
return false;
else
{
for(int i = length -1; i >= 0; i--)
{
if(digit[i] != b.digit[i])
return false;
}
}
return true;
}
BigInteget BigInteget::operator+(const BigInteget& b)
{
BigInteget answer;
int carry = 0;
for(int i = 0; i < length || i < b.length; i++)
{
int current = carry + digit[i] + b.digit[i];
carry = current /10;
answer.digit[answer.length++] = current % 10;
}
if(carry)
{
answer.digit[answer.length++] = carry;
}
return answer;
}
BigInteget BigInteget::operator-(const BigInteget& b)
{
BigInteget answer;
int carry = 0;
for(int i = 0; i < length; i++)
{
int current = digit[i] - b.digit[i] - carry;
if(current < 0)
{
current += 10;
carry = 1;
}
else
carry = 0;
answer.digit[answer.length++] = current;
}
while(answer.digit[answer.length-1] == 0 && answer.length > 1)
{// answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator*(const BigInteget& b)
{
BigInteget answer;
answer.length = length + b.length;
for(int i = 0; i < length; i++)
{
for(int j = 0; j < b.length; j++)
answer.digit[i+j] += digit[i] * b.digit[j];
}
for(int i = 0; i < answer.length; i++)
{
answer.digit[i+1] += answer.digit[i] / 10;
answer.digit[i] %= 10;
}
while(answer.digit[answer.length-1] == 0 && answer.length > 1)
{ // answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator/(const BigInteget& b)
{
BigInteget answer;
answer.length = length;
BigInteget remainder = 0;
BigInteget temp = b;
for(int i = length -1; i >= 0; i--)
{
if(!(remainder.length == 1 && remainder.digit[0] == 0))
{
for(int j = remainder.length -1; j >= 0; j--)
remainder.digit[j+1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while(temp <= remainder)
{
remainder = remainder - temp;
answer.digit[i]++;
}
}
while(answer.digit[answer.length-1] == 0 && answer.length > 1)
{// answer.digit[answer.length]
answer.length--;
}
return answer;
}
BigInteget BigInteget::operator%(const BigInteget &b)
{
BigInteget remainder = 0;
BigInteget temp = b;
for(int i = length -1; i >= 0; i--)
{
if(!(remainder.length == 1 && remainder.digit[0] == 0))
{
for(int j = remainder.length - 1; j >= 0; j--)
remainder.digit[j+1] = remainder.digit[j];
remainder.length++;
}
remainder.digit[0] = digit[i];
while(temp <= remainder)
{
remainder = remainder - temp;
}
}
return remainder;
}
int main()
{
BigInteget a, b;
cin >> a >> b;
cout << a + b << endl;
cin >> a >> b;
cout << a - b << endl;
cin >> a >> b;
cout << a * b << endl;
cin >> a >> b;
cout << a / b << endl;
cin >> a >> b;
cout << a % b << endl;
return 0;
}