c++大整数クラスのいくつかの実現方法と解析
8720 ワード
ojで問題を作る時、みんなは多くの大きい整数を要求する問題に出会ったことがあると信じて、この時、私達はいわゆる高精度のアルゴリズムを使う必要があって、つまり配列で整数を貯蔵して、4則の演算とその他のよくある演算をシミュレートして、以下はいくつかの大きい整数を実現する方法を分析します
一.大きな整数をvectorで格納
このコードは私がアルゴリズムコンテストを参照して入門したものです.次に、具体的な実現過程を分析します.
まずbase=1億円、width=8を定義し、8ビットごとにintで大きな整数をvectorに保存し、付与演算子を再ロードして文字列を入力することで文字列をvectorコンテナ値に変換します.
次に加算の重荷実装を行い,8ビットを取るごとに+演算を行い,結果が8ビットを超えると1ビット進み,そのビットを次の演算に残す.
減算のリロードは、8ビットずつ取り出して−演算を行い、結果が0未満であればs[i+1]、すなわちvector容器内の後の値から1000000を取り出して計算し、s[i+1]であれば減算してビットを実現する.
二.大きな整数を配列で格納
これは配列によって大きな整数を格納し,配列の各空間に1つの数字を格納することで,大きな整数を保存する目的を達成する.
大整数加算減算法の実現は,前述の基本と同様に,ビットイン,ビットダウンのシミュレーションにより実現される.
次に、乗算の実現過程を説明します.乗算の実現は、手算をシミュレートする方法で、最初の数の各ビットに、2番目の数の各ビットを乗算し、最後にまとめ、結果を算出します.
法則を除くのは4つの演算の中で最も複雑な1つで、基本的な考え方は1つ1つ減らして、最大でどれだけの除数を減らすことができるかを見て、しかし明らかにこのようにすると効率はまったく極めて低いです.どのようにしてもっと速く減らしますか?7546を23で割った例で見ると、開始商は0です.まず23の100倍を引くと2300になり、3回減らすことができ、残りは646だった.すると商の値は300増加します.その後646で230を引くと、2回減らすことができ、残りの186は、商の値が20増加した.最後に186で23を減らして8回減らすことができるので、最終商は328です.
上はまさにこのような考えを使っています.
一.大きな整数をvectorで格納
#include
#include
#include
#include
#include
#include
using namespace std;
class BigInteger
{
public:
static const int base=100000000;
static const int width=8;
vectors;
BigInteger(long long num=0){*this=num;} //
BigInteger operator=(long long num)
{
s.clear();
do{
s.push_back(num%base);
num=num/base;
}while(num>0);
return *this;
}
BigInteger operator=(const string &str) // =
{
s.clear();
int x,len=(str.length()-1)/width+1;
for(int i=0;i=0;i--){
char buf[20];
sprintf(buf,"%08d",x.s[i]);
for(int j=0;j>(istream &in,BigInteger& x) //
{
string s;
if(!(in>>s)) return in;
x=s;
return in;
}
BigInteger operator+(const BigInteger& b)const //
{
BigInteger c;
c.s.clear();
for(int i=0,g=0;;i++){
if(g==0&&i>=s.size()&&i>=b.s.size()) break;
int x=g;
if(ib){
int i,g;
for(i=0,g=0;;i++){
if(g==0&&i>=b.s.size()) break;
int x=g;
if(s[i]=0;i--)
if(s[i]!=b.s[i]) return s[i](const BigInteger& b)const //
{
return b=(const BigInteger& b)const
{
return !(*this このコードは私がアルゴリズムコンテストを参照して入門したものです.次に、具体的な実現過程を分析します.
まずbase=1億円、width=8を定義し、8ビットごとにintで大きな整数をvectorに保存し、付与演算子を再ロードして文字列を入力することで文字列をvectorコンテナ値に変換します.
次に加算の重荷実装を行い,8ビットを取るごとに+演算を行い,結果が8ビットを超えると1ビット進み,そのビットを次の演算に残す.
減算のリロードは、8ビットずつ取り出して−演算を行い、結果が0未満であればs[i+1]、すなわちvector容器内の後の値から1000000を取り出して計算し、s[i+1]であれば減算してビットを実現する.
二.大きな整数を配列で格納
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX_L 2005
using namespace std;
class bign
{
public:
int len, s[MAX_L];// ，
//
bign();
bign(const char*);
bign(int);
bool sign;// 1 0
string toStr() const;// ，
friend istream& operator>>(istream &,bign &);//
friend ostream& operator<(const bign &) const;
bool operator>=(const bign &) const;
bool operatorb ? a : b
#define min(a,b) a>(istream &in, bign &num)
{
string str;
in>>str;
num=str;
return in;
}
ostream &operator<= 0; i--)
if (s[i] != num.s[i])
return sign ? (s[i] < num.s[i]) : (!(s[i] < num.s[i]));
return !sign;
}
bool bign::operator>(const bign&num)const
{
return num < *this;
}
bool bign::operator<=(const bign&num)const
{
return !(*this>num);
}
bool bign::operator>=(const bign&num)const
{
return !(*this num || *this < num;
}
bool bign::operator==(const bign&num)const
{
return !(num != *this);
}
bign bign::operator+(const bign &num) const
{
if (sign^num.sign)
{
bign tmp = sign ? num : *this;
tmp.sign = 1;
return sign ? *this - tmp : num - tmp;
}
bign result;
result.len = 0;
int temp = 0;
for (int i = 0; temp || i < (max(len, num.len)); i++)
{
int t = s[i] + num.s[i] + temp;
result.s[result.len++] = t % 10;
temp = t / 10;
}
result.sign = sign;
return result;
}
bign bign::operator++()
{
*this = *this + 1;
return *this;
}
bign bign::operator++(int)
{
bign old = *this;
++(*this);
return old;
}
bign bign::operator+=(const bign &num)
{
*this = *this + num;
return *this;
}
bign bign::operator-(const bign &num) const
{
bign b=num,a=*this;
if (!num.sign && !sign)
{
b.sign=1;
a.sign=1;
return b-a;
}
if (!b.sign)
{
b.sign=1;
return a+b;
}
if (!a.sign)
{
a.sign=1;
b=bign(0)-(a+b);
return b;
}
if (a= 0) g = 0;
else
{
g = 1;
x += 10;
}
result.s[result.len++] = x;
}
result.clean();
return result;
}
bign bign::operator * (const bign &num)const
{
bign result;
result.len = len + num.len;
for (int i = 0; i < len; i++)
for (int j = 0; j < num.len; j++)
result.s[i + j] += s[i] * num.s[j];
for (int i = 0; i < result.len; i++)
{
result.s[i + 1] += result.s[i] / 10;
result.s[i] %= 10;
}
result.clean();
result.sign = !(sign^num.sign);
return result;
}
bign bign::operator*(const int num)const
{
bign x = num;
bign z = *this;
return x*z;
}
bign bign::operator*=(const bign&num)
{
*this = *this * num;
return *this;
}
bign bign::operator /(const bign&num)const
{
bign ans;
ans.len = len - num.len + 1;
if (ans.len < 0)
{
ans.len = 1;
return ans;
}
bign divisor = *this, divid = num;
divisor.sign = divid.sign = 1;
int k = ans.len - 1;
int j = len - 1;
while (k >= 0)
{
while (divisor.s[j] == 0) j--;
if (k > j) k = j;
char z[MAX_L];
memset(z, 0, sizeof(z));
for (int i = j; i >= k; i--)
z[j - i] = divisor.s[i] + '0';
bign dividend = z;
if (dividend < divid) { k--; continue; }
int key = 0;
while (divid*key <= dividend) key++;
key--;
ans.s[k] = key;
bign temp = divid*key;
for (int i = 0; i < k; i++)
temp = temp * 10;
divisor = divisor - temp;
k--;
}
ans.clean();
ans.sign = !(sign^num.sign);
return ans;
}
bign bign::operator/=(const bign&num)
{
*this = *this / num;
return *this;
}
bign bign::operator%(const bign& num)const
{
bign a = *this, b = num;
a.sign = b.sign = 1;
bign result, temp = a / b*b;
result = a - temp;
result.sign = sign;
return result;
}
bign bign::pow(const bign& num)const
{
bign result = 1;
for (bign i = 0; i < num; i++)
result = result*(*this);
return result;
}
bign bign::factorial()const
{
bign result = 1;
for (bign i = 1; i <= *this; i++)
result *= i;
return result;
}
void bign::clean()
{
if (len == 0) len++;
while (len > 1 && s[len - 1] == '\0')
len--;
}
bign bign::Sqrt()const
{
if(*this<0)return -1;
if(*this<=1)return *this;
bign l=0,r=*this,mid;
while(r-l>1)
{
mid=(l+r)/2;
if(mid*mid>*this)
r=mid;
else
l=mid;
}
return l;
}
bign::~bign()
{
} これは配列によって大きな整数を格納し,配列の各空間に1つの数字を格納することで,大きな整数を保存する目的を達成する.
大整数加算減算法の実現は,前述の基本と同様に,ビットイン,ビットダウンのシミュレーションにより実現される.
次に、乗算の実現過程を説明します.乗算の実現は、手算をシミュレートする方法で、最初の数の各ビットに、2番目の数の各ビットを乗算し、最後にまとめ、結果を算出します.
法則を除くのは4つの演算の中で最も複雑な1つで、基本的な考え方は1つ1つ減らして、最大でどれだけの除数を減らすことができるかを見て、しかし明らかにこのようにすると効率はまったく極めて低いです.どのようにしてもっと速く減らしますか?7546を23で割った例で見ると、開始商は0です.まず23の100倍を引くと2300になり、3回減らすことができ、残りは646だった.すると商の値は300増加します.その後646で230を引くと、2回減らすことができ、残りの186は、商の値が20増加した.最後に186で23を減らして8回減らすことができるので、最終商は328です.
上はまさにこのような考えを使っています.