算法之大数加减乘除

大数加法：

　　例题 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] = '\0';//字符串倒转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:\n",t);printf("%s + %s = %s\n",sa,sb,res);if(t!=T)printf("\n");}return 0; } View Code

 

大数减法：

    这几天比较忙，大数减法到现在开始写。大数减法大体思路与大数加法类似。主要是确定相减的两个数的大小，然后总是大的减小的，最后所得结果更加判断是否减少负号。

#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] = '\0';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';}//去多余0while(res[k-1]=='0')--k;if(sign == '-')res[k++] = sign;res[k] = '\0';Reverse(res); } int main() {char s1[100],s2[100],res[100];while(~scanf("%s%s",s1,s2)){big_sub(res,s1,s2);printf("%s\n",res);}return 0; } View Code

 

大数乘法：

　　方法一：计算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] = '\0';Reverse(res); }int main() {char res[201],s1[100],s2[100];while(~scanf("%s%s",s1,s2)){big_mul(res,s1,s2);printf("%s\n",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] = '\0';strcpy(s,temp); } View Code

 

转载于:https://www.cnblogs.com/jlyg/p/6668347.html

总结

以上是生活随笔为你收集整理的算法之大数加减乘除的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。