?? biginteger.h
字號:
ret = false;
else if (a.Length() < b.Length())
ret = true;
else
for (int i = a.Length(); i >=1 ; i--)
if (a.GetData(i) > b.GetData(i)) {
ret = false;
break;
}
else if (a.GetData(i) < b.GetData(i)) {
ret = true;
break;
}
}
else{ //a and b are minus
if (a.Length() > b.Length())
ret = true;
else if (a.Length() < b.Length())
ret = false;
else
for (int i = 1; i <= a.Length(); i++)
if (a.GetData(i) > b.GetData(i)) {
ret = true;
break;
}
else if (a.GetData(i) < b.GetData(i)) {
ret = false;
break;
}
}
return ret;
}
template <class T>
bool BigInteger<T>::operator == (const BigInteger<T>& obj){
bool ret = true;
BigInteger<T> a(*this), b(obj);
a = standardize(a);
b = standardize(b);
if (a.GetSymbol() == b.GetSymbol() && a.Length() == b.Length()) {
for (int i = 0; i <= Last; i++){
if (Data[i] != obj.GetData(i + 1)) {
ret = false;
break;
}
}
}
else
ret = false;
return ret;
}
template <class T>
void BigInteger<T>::Input(){
cout<<"Please input the symbol of big integer('+' or 'minus'):";
while (1) {
char smbl;
cin>>smbl;
if ('+' == smbl) {
Symbol = PLUS;
break;
}
if ('-' == smbl) {
Symbol = MINUS;
break;
}
cout<<"Input symbol invalid,please input again."<<endl;
}
cout<<"please input the length of big integer:";
while (1) {
cin>>Last;
if (Last <= MaxSize - 1) break;
cout<<"Input length isn't allowed greater than maximal size: "<<MaxSize - 1
<<"Please input again"<<endl;
}
for (int i = 0; i < Last; i++)
cin>>Data[i];
}
template <class T>
void BigInteger<T>::Output(){
cout<<"the big integer is: ";
if (Symbol == MINUS)
cout<<'-';
for (int i = Last; i >= 0; i--)
cout<<Data[i];
cout<<endl;
}
template <class T>
ifstream& operator >>(ifstream& in, BigInteger<T>& obj){
string str;
getline(in,str,'\n');
int bufSize = 0;
int smblflag = 0;
int strLen = str.length();
SYMBOL smbl;
switch(str[0]) {
case '-':
smbl =MINUS;
smblflag = 1;
bufSize = strLen;
break;
case '+':
smbl = PLUS;
smblflag = 1;
bufSize = strLen;
break;
default:
smbl = PLUS;
bufSize = strLen + 1;
smblflag = 0;
}
T* buf = new T[bufSize];
buf[bufSize - 1] = 0;
for (int i = smblflag; i < bufSize - 1 + smblflag; i++)
buf[bufSize - 2 - i + smblflag] = str[i];
BigInteger<T> num(buf,smbl);
obj = num;
return in;
}
template <class T>
ofstream& operator <<(ofstream& out,const BigInteger<T>& obj){
bool flag = true;
if (obj.GetSymbol() == MINUS)
out<<'-';
for (int i = obj.Length(); i >= 1; i--){
if (obj.GetData(i) == '0' && flag) continue;
out<<obj.GetData(i);
flag = false;
}
out<<endl;
return out;
}
int MinKthPower(int a, int b, const int& k){
int ret = 0;
int n = 0;
if (k <= 0){
cerr<<"Invalid value of the third parameters!"<<endl;
exit(1);
}
if (a < k || b < k)
return k;
if (k == 1)
return a > b ? a : b;
while (++n){
ret = pow(k,n);
if (ret >= a && ret >= b)
break;
}
return ret;
}
template <class T>
BigInteger<T> abs(const BigInteger<T>& obj){
BigInteger<T> ret(obj);
if (ret.GetSymbol() == MINUS) {
ret.SetSymbol(PLUS);
}
return ret;
}
template <class T>
BigInteger<T> standardize(const BigInteger<T>& obj) {
BigInteger<T> ret(obj);
for (int i = ret.Length(); i >= 1; i--) {
if (ret.GetData(i) != '0') break;
ret.SetLength(i - 1);
}
return ret;
}
template <class T>
BigInteger<T> PositiveIntSubstraction(const BigInteger<T>& X, const BigInteger<T> &Y) {
BigInteger<T> ret, a(X), b(Y);
SYMBOL sret = PLUS;
if (a.GetSymbol() != PLUS || b.GetSymbol() != PLUS) {
cerr<<"Invalid symbol of the parameter in PositiveIntSubstraction!"<<endl;
exit(1);
}
if (a == b)
return a.ZERO();
BigInteger<T> tmp;
if (a < b) { //如果a < b, 交換a，b
tmp = a;
a = b;
b = tmp;
sret = MINUS;
}
int Len1 = a.Length(), Len2 = b.Length();
b.SetLength(Len1);
ret.SetLength(Len1);
char ch;
bool* C = new bool[Len1 + 1];
C[0] = 0;
for (int i = 1; i <= Len1; i++) {
ch = a.GetData(i) - b.GetData(i) - C[i - 1] + 58;
if (ch >= 48 && ch <= 57) {
C[i] = 1;
}
else {
C[i] = 0;
ch -= 10;
}
ret.SetData(i,ch);
}
delete []C;
ret.SetSymbol(sret);
return ret;
}
template <class T>
BigInteger<T> TraditionalMultiplication(const BigInteger<T>& a, const BigInteger<T>& b){
BigInteger<T> ret, tmp;
int Len1 = a.Length();
int Len2 = b.Length();
ret.SetLength(Len1 + Len2);
tmp.SetLength(Len1 + Len2);
int* c = new int[Len1 + 1];
int m;
for (int j = 1; j <= Len2; j++){
c[0] = 0;
tmp.FillNumber('0');
for (int i = 1; i <= Len1; i++){
m = (a.GetData(i) - 48) * (b.GetData(j) - 48) + c[i - 1];
c[i] = m / 10;
tmp.SetData(i + j - 1,m % 10 + 48);
}
if (c[Len1])
tmp.SetData(Len1 + j, 48 + c[Len1]);
ret = ret + tmp;
}
delete []c;
ret.SetSymbol(a.GetSymbol() == b.GetSymbol() ? PLUS : MINUS);
return ret;
}
template <class T>
BigInteger<T> OptimizedMultiplication(const BigInteger<T>& a, const BigInteger<T>& b, int div/* = 2*/){
BigInteger<T> ret, X(a), Y(b);
X = standardize(X);
Y = standardize(Y);
int originLen = MinKthPower(X.Length(), Y.Length(), div); //返回大于len1和len2的最小的2冪次的整數
X.SetLength(originLen); //make up the shorted number same as the longer one
Y.SetLength(originLen);
if (div == 1 || originLen == div) //對問題沒有劃分或問題規模達到默認的div長度時，直接運算
ret = TraditionalMultiplication(X, Y);
else{
int dividedLen = originLen / div;
BigInteger<T>* M = new BigInteger<T>[div];
BigInteger<T>* N = new BigInteger<T>[div];
for (int j = 0; j < div; j++) {
M[j].SetLength(dividedLen);
N[j].SetLength(dividedLen);
for (int i = 1; i <= dividedLen; i++) {
M[j].SetData(i, X.GetData(i + dividedLen * j));
N[j].SetData(i, Y.GetData(i + dividedLen * j));
}
}
ret = OptimizedFuncion(M, N, originLen, div);
ret.SetSymbol(X.GetSymbol() == Y.GetSymbol() ? PLUS : MINUS);
delete []M;
delete []N;
}
return ret;
}
template <class T>
BigInteger<T> LeftShift(const BigInteger<T>&a, int n) {
BigInteger<T> ret;
ret.SetSymbol(a.GetSymbol());
ret.SetLength(a.Length() + n);
for (int j = 1; j <= n; j++)
ret.SetData(j,'0');
for (int i = 1; i <= a.Length(); i++)
ret.SetData(i + n, a.GetData(i));
return ret;
}
template <class T>
BigInteger<T> OptimizedFuncion(BigInteger<T> M[], BigInteger<T> N[], int originLen, int div) {
BigInteger<T> ret;
int dividedLen = originLen / div;
BigInteger<T> c0,c1,c2,c3,d0,d1,d2,d3,d4,d5,d6;
switch(div) {
case 2:
//////////////////////////////////////////////////////////////////////////
//Formula when divide with 2
//def:n2 = dividedLen / div
//M * N = (M0 + M1 * 10^n2) * (N0 + N1 * 10^n2)
// = M0 * N0 + (M0 * N1 + M1 * N0) * 10^n2 + M1 * N1 * 10^(2*N2)
// = M0 * N0 + [(M0 + M1) * (N0 + N1) - M0 * N0 - M1 * N1] * 10^n2 + M1 * N1 * 10^(2*N2)
//////////////////////////////////////////////////////////////////////////
c0 = M[0] * N[0];
c1 = M[1] * N[1];
d0 = c0;
d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1;
d2 = c1;
ret = LeftShift(d2, 2 * dividedLen) + LeftShift(d1, dividedLen) + d0;
break;
case 3:
//////////////////////////////////////////////////////////////////////////
//Formula when divide with 3
//def:n3 = dividedLen / div
//M * N = [M0 + M1 * 10^n3 + M2 * 10^(2*n3)] * [N0 + N1 * 10^n3 + N2 * 10^(2*n3)]
// = M0 * N0 + (M0 * N1 + M1 * N0) * 10^n3 + (M0 * N2 + M2 * N0 + M1 * N1) * 10^(2*n3) +
// (M1 * N2 + M2 * N1) * 10^(3*n3) + M2 * N2 * 10^(4*n3)
// = M0 * N0 + [(M0 + M1) * (N0 + N1) - M0 * N0 - M1 * N1] * 10^n3 +
// [(M0 + M2) * (N0 + N2) + M1 * N1 - M0 * N0 - M2 * N2) * 10^(2*n3) +
// [(M1 + M2) * (N1 + N2) - M1 * N1 - M2 * N2] * 10^(3*n3) + M2 * N2 * 10^(4*n3)
//////////////////////////////////////////////////////////////////////////
c0 = M[0] * N[0];
c1 = M[1] * N[1];
c2 = M[2] * N[2];
d0 = c0;
d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1;
d2 = (M[0] + M[2]) * (N[0] + N[2]) + c1 - c0 - c2;
d3 = (M[1] + M[2]) * (N[1] + N[2]) - c1 - c2;
d4 = c2;
ret = d0 + LeftShift(d1, dividedLen) + LeftShift(d2, 2 * dividedLen) + LeftShift(d3, 3 * dividedLen) +
LeftShift(d4, 4 * dividedLen);
break;
case 4:
// 算式錯誤！ [10/15/2008]
c0 = M[0] * N[0];
c1 = M[1] * N[1];
c2 = M[2] * N[2];
c3 = M[3] * N[3];
d0 = c0;
d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1;
d2 = (M[0] + M[2]) * (N[0] + N[2]) + c1 - c0 - c2;
d3 = (M[0] + M[3]) * (N[0] + N[3]) + (M[1] + M[3]) * (N[1] + N[3]) - c0 - c1 - c2 -c3;
d4 = (M[1] + M[3]) * (N[1] + N[3]) + c2 - c1 - c3;
d5 = (M[2] + M[3]) * (N[2] + N[3]) - c2 - c3;
d6 = c3;
ret = d0 + LeftShift(d1,dividedLen) + LeftShift(d2, 2 * dividedLen) + LeftShift(d3, 3 * dividedLen) +
LeftShift(d4, 4 * dividedLen) + LeftShift(d5, 5 * dividedLen) + LeftShift(d6, 6 * dividedLen);
break;
default:
cerr<<"can not deal with this partition, div = "<<div<<endl;
exit(1);
break;
}
return ret;
}
template <class T>
BigInteger<T> BigInteger<T>::ZERO() {
BigInteger<T> ret(1);
ret.SetLength(1);
return ret;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -