大数类程序(zz)

技术2022-05-11 67

文章来源: http://bbs.tarena.com.cn/topic.cgi?forum=2&topic=1782

整理了一下, 并为larnum类中逻辑运算符函数添加返回值类型:bool , 并在VS2005下测试过. 分三个文件存放:

Bignum.h // 声明大数类larnum

Bignum.cpp // 实现class larnum

testBignum.cpp // 在main中测试class larnum

****************************** Bignum.h **********************************

/*********************************************Header file of class large intergal number**Used to calculate accurately**File name: larnum.h**Designed by Krizalid on Nov 12th 2004**Latest edition on Apr 16th 2005*******************************************/ // #ifndef LARGE_NUMBER_H // #define LARGE_NUMBER_H #include < iostream > #include < memory.h > #include < stdlib.h > using namespace std; struct divided; // 声明商和余数的结构体 class larnum {public: larnum () //无参数构造函数 { sign = false; digit = new short(0); len = 1; } // larnum larnum (bool n,short b,short *a); //逐个输入成员的构造函数 larnum (char *c); //字符串参数构造函数 larnum (int n); //整型变量构造函数 larnum (larnum & n); //拷贝构造函数 ~larnum(){delete []digit;} //析构函数 friend ostream & operator << (ostream & out,larnum & n); //输出符重载 friend istream & operator >> (istream & in,larnum & n); //输入符重载 short getlen() //取长度 { return len; } larnum & operator = (larnum & b); //运算符重载 larnum operator = (int b); friend larnum abs (larnum n); friend larnum operator + (larnum a,larnum b); friend larnum operator - (larnum a,larnum b); friend larnum operator - (larnum & a); friend larnum operator * (larnum a,larnum b); friend larnum operator / (larnum a,larnum b); friend larnum operator % (larnum a,larnum b); friend larnum power (larnum a,int n); friend larnum operator ++ (larnum & a); friend larnum operator ++ (larnum & a,int); friend larnum operator -- (larnum & a); friend larnum operator -- (larnum & a,int); friend bool operator ! (const larnum & a); friend bool operator == (const larnum & a,const larnum & b); friend bool operator != (const larnum & a,const larnum & b); friend bool operator < (larnum a,larnum b); friend bool operator > (larnum a,larnum b); friend bool operator <= (larnum a,larnum b); friend bool operator >= (larnum a,larnum b); friend larnum operator += (larnum & a,larnum b); friend larnum operator -= (larnum & a,larnum b); friend larnum operator *= (larnum & a,larnum b); friend larnum operator /= (larnum & a,larnum b); friend larnum operator %= (larnum & a,larnum b); friend void swap(larnum & a,larnum & b);private: friend divided divide (larnum & a,larnum & b); //可同时返回商和余数的除法函数 short *digit; //指向最低位数的指针 int len; //长度 bool sign; //符号,false为正,true为负} ; // 定义商和余数的结构体 struct divided { larnum p,r;} ;

****************************** Bignum.cpp **********************************

/************************************ *文件名:Bignum.cpp *功能:class larnum 的实现 *创建日期:2007-9-28************************************/ #include " Bignum.h " // larnum类的实现 larnum::larnum( bool n, short b, short * a) { sign = n; len = b; digit = new short [b]; for (short i = 0;i < b;i++) digit[i] = a[i];} larnum::larnum ( char * c) { int i; char *d = c; if (*d == '-') { sign = true; d++; } else { sign = false; if (*d == '+') d++; } for (i = 0; (*d); d++) if (*d >= '0' && *d <= '9') i++; len = i; digit = new short[i]; for (i = 0;d >= c;d--) if (*d >= '0' && *d <= '9') { digit[i] = *d - '0'; i++; } while (!digit[len - 1]) //判断首位是否为零并作出相应处理 len--; if (len <= 0) { len = 1; sign = false; }} // larnum larnum::larnum( int n) { if (n >= 0) sign = false; else { sign = true; n = -n; } int m = n; for (len = 0;n;len++,n /= 10) ; if (!len) len++; digit = new short[len]; for (short i = 0;i < len;i++) { digit[i] = m % 10; m /= 10; }} larnum::larnum (larnum & n) { sign = n.sign; len = n.len; digit = new short[len]; memcpy(digit,n.digit,2 * len);} larnum & larnum:: operator = (larnum & b) { sign = b.sign; len = b.len; digit = new short[len]; memcpy(digit,b.digit,2 * len); return *this;} larnum larnum:: operator = ( int b) { larnum c(b); *this = c; return *this;} larnum abs (larnum n) { n.sign = 0; return n;} bool operator ! ( const larnum & a) { if ((a.len == 1) && !*a.digit) return true; else return false;} ostream & operator << (ostream & out ,larnum & n) { if (n.sign) out <<"-"; for(short i = n.len - 1;i >= 0;i--) out <<n.digit[i]; return out;} istream & operator >> (istream & in ,larnum & n) {/* const int N = 30;PUl char *k = new char[N];;"fIL char temp, *p = k;F0Mq int l = 1;L$j6,E while ((temp = cin.get()) != ' ');d {N, if (!(l % N))T' {ohJ k = new char[l + N];]5%2IX memcpy (k,p,sizeof(short) * l);T%5 delete []p;Cg p = k;$Pt:Q3 }w]2 k[l - 1] = temp;~`BA l++;F }=TO[h n = larnum(k);M1%u"1 return in;*/ char k[256]; in >>k; n = larnum (k); return in;} // 交换函数 inline void swap(larnum & a,larnum & b) { bool sign = a.sign; a.sign = b.sign; b.sign = sign; short *digit = a.digit; int len = a.len; a.digit = b.digit; b.digit = digit; a.len = b.len; b.len = len;} bool operator == ( const larnum & a, const larnum & b) { if (a.sign ^ b.sign) return false; if (a.len != b.len) return false; for (short i = 0;i <= a.len - 1;i++) if (a.digit[i] != b.digit[i]) return false; return true;} bool operator != ( const larnum & a, const larnum & b) { if (a == b) return false; else return true;} inline larnum operator - (larnum & a) { if (a.len == 1 && !(a.digit[0])) return a; else if (a.sign) a.sign = false; else a.sign = true; return a;} bool operator > (larnum a,larnum b) { switch (2 * a.sign + b.sign) //把符号组合看成二进制数,方便控制,下同w22p. { case 1: return true; case 2: return false; case 3: //若均为负则交换,下面比较的实际上是绝对值NbZ/C swap (a,b); case 0: if (a.len > b.len) return true; //比较长度cX2 else if (a.len < b.len) return false; else { for (int i = a.len - 1;i >= 0;i--) //逐位比较0 { if (a.digit[i] > b.digit[i]) return true; if (a.digit[i] < b.digit[i]) return false; } }// else return false; } // switch} bool operator < (larnum a,larnum b) { return !(a > b || a == b);} bool operator >= (larnum a,larnum b) { return (a > b || a == b);} bool operator <= (larnum a,larnum b) { return !(a > b);} larnum operator + (larnum a,larnum b) { larnum c; short i,l,pro; switch (2 * a.sign + b.sign) { case 0: case 3: //绝对值相加 c.sign = a.sign; if (a.len < b.len) swap(a,b); l = a.len; pro = 0; //进位值 c.digit = new short[l + 1]; for (i = 0;i <= l - 1;i++) { c.digit[i] = a.digit[i] + pro + (i < b.len?b.digit[i]:0); //判断i是否越界 if (c.digit[i] > 9) //判断进位并作出相应处理 { pro = 1; c.digit[i] -= 10; } else pro = 0; } // for if (pro) //根据最后进位值确定结果的长度 { c.digit[l] = 1; c.len = l + 1; } else c.len = l; return c; case 2: swap(a,b); case 1: //绝对值相减 if (-b > a) //以下仅适用于|a| >= |b|,若|a| < |b|则交换 { c.sign = true; swap (a,b); } else c.sign = false; l = a.len; pro = 0; //退位值 c.digit = new short[l]; for (i = 0;i <= l - 1;i++) { c.digit[i] = a.digit[i] + pro - (i < b.len? b.digit[i]:0); //判断i是否越界 if (c.digit[i] < 0) //判断退位并作出相应处理 { pro = -1; c.digit[i] += 10; } else pro = 0; } while (!c.digit[l - 1]) //确定结果的长度 l--; if (!l) l = 1; c.len = l; return c; } // switch} larnum operator += (larnum & a,larnum b) { a = a + b; return a;} larnum operator - (larnum a,larnum b) { return a + (-b);} larnum operator -= (larnum & a,larnum b) { a = a + (-b); return a;} larnum operator * (larnum a,larnum b) { int i, j; if (!a || !b) //对因数有零的先处理 return 0; larnum c; int pro = 0; //进位值 c.sign = a.sign ^ b.sign; //确定符号 short l = a.len + b.len; c.digit = new short[l]; memset(c.digit,0,l * sizeof(short)); //对结果数组清零 for (i = 0; i < a.len; i++) { for (j = 0; j < b.len; j++) { c.digit[i + j] += (a.digit[i] * b.digit[j] + pro); pro = c.digit[i + j] / 10; //进位处理 c.digit[i + j] %= 10; } c.digit[i + j] = pro; pro = 0; } if (c.digit[l - 1]) //确定结果的长度 c.len = l; else c.len = l - 1; return c;} larnum operator *= (larnum & a,larnum b) { a = a * b; return a;} // 用模拟人工笔算实现除法5E divided divide (larnum & a,larnum & b) { divided c; c.r = c.p = 0; if (!b) //判断除零异常 throw b; if (abs(b) > abs(a)) //预先处理处理被除数绝对值小于除数绝对值的情况 { c.r = a; return c; } bool rsign = a.sign; //预先判断和保存结果的符号,以下用绝对值来除 c.p.sign = a.sign ^ b.sign; a = abs(a); b = abs(b); larnum temp; //定义当前除到的数 temp.sign = false; temp.len = b.len; temp.digit = a.digit + a.len - b.len; //指向当前除到的数的末位 c.p.len = a.len - b.len + 1; if (temp < b) { temp.len++; temp.digit--; c.p.len--; } c.p.digit = new short[c.p.len]; //分配商指针 memset (c.p.digit,0,c.p.len * sizeof(short)); //给商指针置零 larnum b_five = b * 5; //定义用于减法的除数的倍数 larnum b_three = b * 5; for (int i = c.p.len - 1;i >= 0;i--) { temp.digit = a.digit + i; temp.len = a.len - i; //用这样的减法,最多四次就能除一位e1[xB if (temp >= b_five) { c.p.digit[i] += 5; temp -= b_five; memcpy (a.digit + i,temp.digit,temp.len * sizeof(short)); a.len = temp.len + i; temp.digit = a.digit + i; } if (temp >= b_three) { c.p.digit[i] += 3; temp -= b_three; memcpy (a.digit + i,temp.digit,temp.len * sizeof(short)); a.len = temp.len + i; temp.digit = a.digit + i; } while (temp >= b) { c.p.digit[i]++; temp -= b; memcpy (a.digit + i,temp.digit,temp.len * sizeof(short)); a.len = temp.len + i; temp.digit = a.digit + i; } while (!a.digit[a.len - 1]) //更新a的长度 a.len--; } // for if (!temp.len) temp.len++; c.r = temp; //最后剩下的就是余数 temp.digit = new short(0); //因temp和a用的是同一块内存,只有这样才能避免析构时不出错 c.r.sign = rsign; //商的符号 return c;} larnum operator / (larnum a,larnum b) { divided c; try //捕捉除零异常 { c = divide(a,b); } catch(larnum) { cerr<<"ERROR: Exception of divided by zero. End. "; exit(1); } return c.p;} larnum operator /= (larnum & a,larnum b) { a = a / b; return a;} larnum operator %= (larnum & a,larnum b) { a = a % b; return a;} larnum operator % (larnum a,larnum b) { divided c; try //捕捉除零异常 { c = divide(a,b); } catch(larnum) { cerr<<"ERROR: Exception of divided by zero. End. "; exit(0); } return c.r;} larnum power (larnum a, int n) { if (n < 0) return 0; larnum b = 1; for (int i = 0;i < n;i++) b *= a; return b;} larnum operator ++ (larnum & a) { int i; switch (a.sign) { case 0: for (i = 0;i < a.len;i++) { a.digit[i]++; if (a.digit[i] != 10) //只要没有进位就可以马上返回 return a; else a.digit[i] = 0; } // for delete []a.digit; //如果每一位都是9才分配新的内存 a.len++; a.digit = new short[a.len]; memset(a.digit,0,a.len * sizeof(short)); a.digit[a.len - 1] = 1; return a; case 1: if (a.len == 1) //预先处理一位数的情形 { if (!(--a.digit[0])) a.sign = 0; return a; } for (i = 0;i < a.len - 1;i++) { a.digit[i]--; if (a.digit[i] != -1) return a; else a.digit[i] = 9; } if (!(--a.digit[i])) a.len--; return a; } // switch} larnum operator ++ (larnum & a, int ) { larnum b = a; ++a; return b;} larnum operator -- (larnum & a) { larnum b = -a; ++b; return a = -b;} larnum operator -- (larnum & a, int ) { larnum b = a; --a; return b;} /*larnum::larnum (char *c){ char *d = c; int i; if (*d == '-') { sign = true; d++; } else { sign = false; if (*d == '+') d++; } for (i = 0; (*d); d++) if (*d >= '0' && *d <= '9') i++; len = i; digit = new short[i]; for (i = 0;d >= c;d--) if (*d >= '0' && *d <= '9') { digit[i] = *d - '0'; i++; } while (!digit[len - 1]) //判断首位是否为零并作出相应处理 len--; if (len <= 0) { len = 1; sign = false; }}*/

****************************** testBignum.cpp **********************************

/************************************ *文件名:testBignum.cpp *功能:测试class larnum *创建日期:2007-9-28************************************/ #include < iostream > #include " Bignum.h " using namespace std; int main() { larnum a,b; cout <<"Please input LargeNumber a: "; cin >>a; cout <<"Please input LargeNumber b: "; cin >>b; int n; cout <<"Please input n: "; cin >> n; cout << "a = " << a << endl; cout <<"b = "<<b<<endl; cout << "Length of a: " << a.getlen() << endl; cout <<"Length of b: "<<b.getlen()<<endl; cout <<"a + b = "<<a + b<<endl; cout <<"a - b = "<<a - b<<endl; cout <<"a * b = "<<a * b<<endl; cout <<"a / b = "<<a / b<<endl; cout <<"a mod b = "<<a % b<<endl; cout << "a ^ " << n << " = " << power(a,n) <<endl; return 0;}

专利

最新回复(0)