Uva--10106 (高精度,大数乘)
2014-06-01 18:03:30
题意 & 思路:大数乘,这里采用的小白书里的bign结构体
#include <cstdio> #include <string> #include <cstring> #include <iostream> using namespace std; const int maxn = 1000; struct bign{ int len,s[maxn + 5]; bign(){ memset(s,0,sizeof(s)); len = 1;//因为0的存在 } bign operator = (const char *num){ len = strlen(num); for(int i = 0; i < len; ++i) s[i] = num[len - i - 1] - \'0\';//倒序转化成数字 return *this; } bign operator = (int num){ char ts[maxn + 5]; sprintf(ts,"%d",num); *this = ts; return *this; } bign(int num){ *this = num; } bign(const char *num){ *this = num; } //bign的str型转化 string str() const{ string res = ""; for(int i = len - 1; i >= 0; --i) res += (char)(s[i] + \'0\'); if(res == "") res = "0"; return res; } //高精度加 bign operator + (const bign & b) const{ bign sum;//保存结果的bign sum.len = 0; for(int i = 0, g = 0; g || i < max(len,b.len); ++i){ int x = g;//x:暂存和,g:进位 if(i < len) x += s[i]; if(i < b.len) x += b.s[i]; sum.s[sum.len++] = x % 10; g = x / 10; } return sum; } //高精度乘,实际上加和乘对进位的处理有所不同,比较喜欢乘的 bign operator * (const bign &b) const{ bign pro; pro.len = 0; for(int i = 0; i < len; ++i){ for(int j = 0; j < b.len; ++j){ pro.s[i + j] += (s[i] * b.s[j]); pro.s[i + j + 1] += pro.s[i + j] / 10; pro.s[i + j] %= 10; } } pro.len = len + b.len + 1;//这里注意pro.len初始值可能是题目数字范围两倍 while(pro.s[pro.len - 1] == 0 && pro.len > 1) --pro.len;//最后一位不管是不是0都不能让len - 1 if(pro.s[pro.len]) ++pro.len;//这句有待商讨 return pro; } //额外加的+=重载 bign operator += (const bign & b){ *this = *this + b; return *this; } //额外的比较运算符重载 bool operator < (const bign & b) const{ if(len != b.len) return len < b.len; for(int i = len - 1; i >= 0; --i)//从高位开始比较 if(s[i] != b.s[i]) return s[i] < b.s[i]; //如果 本身 == b return false; } bool operator > (const bign &b) const{ return b < *this;//代表 本身 > b } bool operator <= (const bign &b) const{ return !(b < *this);//带表 !(本身 > b) } bool operator >= (const bign &b) const{ return !(*this < b); } bool operator != (const bign &b) const{ return *this < b || b < *this; } bool operator == (const bign &b) const{ return !(*this < b) && !(b < *this); } friend istream & operator >> (istream & in,bign & x); friend ostream & operator << (ostream & out,const bign & x); }; istream & operator >> (istream & in,bign & x){ string ts; in >> ts; x = ts.c_str(); return in; } ostream & operator << (ostream & out,const bign & x){ out << x.str(); return out; } int main(){ char st1[maxn + 5],st2[maxn + 5]; bign n1,n2; while(scanf("%s%s",st1,st2) == 2){ n1 = st1; n2 = st2; cout << n1 * n2 << endl; } return 0; }
版权声明:本文为naturepengchen原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。