大数加法：
例题 hdu1002
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N (1010) void big_add(char* res,char* sa,char* sb) { //add为进位，k表示res长度。 int ia,ib,add,k; ia = strlen(sa)-1; //从长度-1开始计算 ib = strlen(sb)-1; k=add = 0; while(ia>=0&&ib>=0) { int num = sa[ia] -'0'+ sb[ib] - '0' + add; add = num / 10; num %= 10; res[k++] = num + '0'; --ia; --ib; } while(ia>=0) { int num = sa[ia] - '0' + add; add = num / 10; num %= 10; res[k++] = num + '0'; --ia; } while(ib>=0) { int num = sb[ib] - '0' + add; add = num / 10; num %= 10; res[k++] = num + '0'; --ib; } if(add != 0) res[k++] = add + '0'; res[k] = ' '; //字符串倒转 char temp[k+1]; strcpy(temp,res); for(int i=k-1;i>=0;--i) res[k-1-i] = temp[i]; } int main() { int T; scanf("%d",&T); for(int t=1;t<=T;++t) { char res[N],sa[N],sb[N]; scanf("%s%s",sa,sb); big_add(res,sa,sb); printf("Case %d: ",t); printf("%s + %s = %s ",sa,sb,res); if(t!=T) printf(" "); } return 0; }
大数减法：
这几天比较忙，大数减法到现在开始写。大数减法大体思路与大数加法类似。主要是确定相减的两个数的大小，然后总是大的减小的，最后所得结果更加判断是否减少负号。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; //字符串反转 void Reverse(char* s) { int k = strlen(s); char temp[k]; for(int i=0;i<k;++i) temp[k-i-1] = s[i]; temp[k] = ' '; strcpy(s,temp); } // res = s1 - s2; void big_sub(char* res,char* s1,char* s2) { //当s1等于s2的时候，直接返回零 if(strcmp(s1,s2)==0) { strcpy(res,"0"); return; } int l1 = strlen(s1),l2 = strlen(s2); char *str1,*str2,sign = '+'; //通过字符串的长度与strcmp比较这个函数，去掉s1与s2是那个大 //该方法总是大的减小的，根据判断，答案是否会加上'-'号。 if(l1 > l2 || (l1==l2&&strcmp(s1,s2)>0)) { str1 = s1; str2 = s2; } else { str1 = s2; str2 = s1; sign = '-'; } int sub=0,k=0; l1 = strlen(str1); l2 = strlen(str2); while(l1&&l2) { int ans = str1[--l1] - str2[--l2] - sub; if(ans < 0) ans += 10,sub = 1; else sub = 0; res[k++] = ans + '0'; } while(l1) { int ans = str1[--l1] - '0' - sub; if(ans < 0) ans += 10,sub = 1; else sub = 0; res[k++] = ans + '0'; } //去多余0 while(res[k-1]=='0') --k; if(sign == '-') res[k++] = sign; res[k] = ' '; Reverse(res); } int main() { char s1[100],s2[100],res[100]; while(~scanf("%s%s",s1,s2)) { big_sub(res,s1,s2); printf("%s ",res); } return 0; }
大数乘法：
方法一：计算a*b的和，只要利用大数加法a相加b次就行了，循环b次的时候可以用大数减法进行--b计算。思路比较简单，但是效率很低，在这里只是稍微提一下而已。
方法二：dp[i+j] += a[i]*b[j] + add;代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; //字符串反转 void Reverse(char* s); //该方法有点像dp void big_mul(char* res,char* s1,char* s2) { if(strcmp(s1,"0")==0||strcmp(s2,"0")==0) { strcpy(res,"0"); return; } int l1 = strlen(s1),l2 = strlen(s2); for(int i=0;i<l1+l2;++i) res[i] = '0'; for(int i=l1-1,ki=0;i>=0;--i,++ki) { int add = 0,kj=0; for(int j=l2-1;j>=0;--j,++kj) { int num = (res[ki+kj]-'0') + (s1[i] - '0') * (s2[j]-'0') + add; add = num / 10; res[ki + kj] = num%10 + '0'; } //kj已经加1了 int k = ki+kj; while(add) { int num = (res[k]-'0') + add; add = num / 10; res[k++] = num%10 + '0'; } } int k = l1 + l2; while(res[k-1] == '0') --k; res[k] = ' '; Reverse(res); } int main() { char res[201],s1[100],s2[100]; while(~scanf("%s%s",s1,s2)) { big_mul(res,s1,s2); printf("%s ",res); } return 0; } void Reverse(char* s) { int k = strlen(s); char temp[k]; for(int i=0;i<k;++i) temp[k-i-1] = s[i]; temp[k] = ' '; strcpy(s,temp); }