杭电acm 1002 大数模板(一)
杭电acm 1002 大数模板(一)
从杭电第一题开始A，发现做到1002就不会了，经过几天时间终于A出来了，顺便整理了一下关于大数的东西
其实这是刘汝佳老师在《算法竞赛 经典入门 第二版》 中所讲的模板，代码原封不动写上的，但是经过自己的使用与调试也明白了其中的内涵。
首先定义大数的结构体：
struct BigNum{ static const int BASE=100000000; static const int WIDTH=8; vector<int> s; BigNum(long long num=0){ *this=num; } BigNum operator = (long long num){ s.clear(); //vector.clear() 移除容器中的元素 do{ s.push_back(num%BASE); //vectro.push_back() 向尾部添加元素 num/=BASE; }while(num>0); return *this; } BigNum operator =(const string& str){ s.clear(); int x,len=(str.length()-1)/WIDTH+1; int mmm=str.length(); for(int i=0;i<len;i++){ int end=str.length()-i*WIDTH; int start=max(0,end-WIDTH); sscanf(str.substr(start,end-start).c_str(),"%d",&x); s.push_back(x); /* *sscanf(str.substr(start,end-start).c_str(),"%d",&x) * *sscanf(a,b,c); *三个参数 将a中的字符串以b的格式写入到c中 * *c_str() 据说是为了和C语言兼容，并不懂，有大神知道还请讲解 * *substr() 复制 */ } return *this; }
View Code
在定义的结构体中，可以将一个大数以字符串的形式输入到结构体BigNum 中的 vector容器中，WIDTH的作用是将这个大数字符串分割成八个字符。
并且在结构体中重载了赋值运算符”=”然后就可以像 BigNum a=”1122334455667789891484684689″ 这样对a进行赋值。
然后重载输入输出流运算符：
ostream& operator << (ostream &out,const BigNum& x){ out<<x.s.back(); //vector.back() 回传最后一个数据 for(int i=x.s.size()-2;i>=0;i--){ char buf[126]; sprintf(buf,"%08d",x.s[i]); for(int j=0;j<strlen(buf);j++) out<<buf[j]; /* *sprintf(a,b,c) 把c中的b格式的数据写入到a中 */ } return out; } istream& operator >>(istream &in,BigNum& x){ string s; if(!(in>>s)) return in; x=s; return in; }
View Code
重载之后，就可以使用 cin>>a; cout<<a; 进行输入输出。
ps:buf的大小是依据题目中的数据的大小而规定的。
重载 “+”:
BigNum operator +(const BigNum& b) const{ BigNum 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(i<s.size()) x+=s[i]; if(i<b.s.size()) x+=b.s[i]; c.s.push_back(x%BASE); g=x/BASE; } return c; }
View Code
附上完整代码：
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <vector> 5 #include <stdio.h> 6 using namespace std; 7 struct BigNum{ 8 static const int BASE=100000000; 9 static const int WIDTH=8; 10 vector<int> s; 11 BigNum(long long num=0){ *this=num; } 12 BigNum operator = (long long num){ 13 s.clear(); //vector.clear() 移除容器中的元素 14 do{ 15 s.push_back(num%BASE); //vectro.push_back() 向尾部添加元素 16 num/=BASE; 17 }while(num>0); 18 return *this; 19 } 20 BigNum operator =(const string& str){ 21 s.clear(); 22 int x,len=(str.length()-1)/WIDTH+1; 23 int mmm=str.length(); 24 for(int i=0;i<len;i++){ 25 int end=str.length()-i*WIDTH; 26 int start=max(0,end-WIDTH); 27 sscanf(str.substr(start,end-start).c_str(),"%d",&x); 28 s.push_back(x); 29 /* 30 *sscanf(str.substr(start,end-start).c_str(),"%d",&x) 31 * 32 *sscanf(a,b,c); 33 *三个参数 将a中的字符串以b的格式写入到c中 34 * 35 *c_str() 据说是为了和C语言兼容，并不懂，有大神知道还请讲解 36 * 37 *substr() 复制 38 */ 39 } 40 return *this; 41 } 42 BigNum operator +(const BigNum& b) const{ 43 BigNum c; 44 c.s.clear(); 45 for(int i=0,g=0;;i++){ 46 if(g==0&&i>=s.size()&&i>=b.s.size()) break; 47 int x=g; 48 if(i<s.size()) x+=s[i]; 49 if(i<b.s.size()) x+=b.s[i]; 50 c.s.push_back(x%BASE); 51 g=x/BASE; 52 } 53 return c; 54 } 55 friend ostream& operator << (ostream &out,const BigNum& x); 56 friend istream& operator >>(istream &in,BigNum& x); 57 }; 58 ostream& operator << (ostream &out,const BigNum& x){ 59 out<<x.s.back(); //vector.back() 回传最后一个数据 60 for(int i=x.s.size()-2;i>=0;i--){ 61 char buf[126]; 62 sprintf(buf,"%08d",x.s[i]); 63 for(int j=0;j<strlen(buf);j++) 64 out<<buf[j]; 65 /* 66 *sprintf(a,b,c) 把c中的b格式的数据写入到a中 67 */ 68 69 } 70 return out; 71 } 72 istream& operator >>(istream &in,BigNum& x){ 73 string s; 74 if(!(in>>s)) return in; 75 x=s; 76 return in; 77 } 78 BigNum a,b,c; 79 string A,B; 80 int main(){ 81 int T; 82 cin>>T; 83 int flag=1; 84 while(T--){ 85 //cin>>A>>B; 86 cin>>a>>b; 87 //a=A; 88 //b=B; 89 c=a+b; 90 cout<<"Case "<<flag<<":"; 91 cout<<endl; 92 //cout<<A<<" "<<"+"<<" "<<B<<" = "; 93 cout<<a<<" "<<"+"<<" "<<b<<" = "; 94 if(T!=0) cout<<c<<endl; 95 else cout<<c; 96 cout<<endl; 97 flag++; 98 } 99 return 0; 100 }
View Code
ps：杭电对输出格式的控制真恐怖！！！
版权声明：本文为hahahameimingzi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。