大数加法乘法

此文转载自http://blog.sina.com.cn/s/blog_698552160100qlwx.html

当我们在做题时可能有时候会遇到数量级很大的比如10^100

^{在对这种数进行处理时显然直接用电脑来计算是不可能的}

^{long long也才64位大约是36893488079550387200才10^20显然不够，}

^{这个时候我们就要用到大数处理了}

^{大数处理的思想是利用数组储存数据，然后模拟小学的加减乘除，各位十位百位……按照位数来做}

由于是用简单加法来模拟所以即使是100亿也是很快的

^{下面我写下我写的大数加法和大数乘法}

^{大数加法，定义两个字符串来读入大数，然后计算出数组长度，用两个整形数组来保存}

^{这里注意从字符到整形用的是<int>(字符)-‘0’来转化，如果直接<int>(字符)得到的会是对应的ＡＳＣＩＩ值}

^{如<int>(‘１’)＝４９而不是１！}

^{然后用数组的第一个元素来保存数据长度}

^{然后就是模拟加法了，用一个循环就行了，对应的位数相加}

^核心算法????????for(inti=1;i<=temp;i++)
???????????????????????c[i]=a[i]+b[i];

一句话

再就是进位的事儿啦>9进1，同时该位变成进位后的，也就是个位上的数用来实现

核心算法?????????for(intj=0;j<=temp+1;j++)
?????????????????????????if(c[j]>9){c[j+1]+=c[j]/10;c[j]%=10;}
然后就是打印了，想想该以怎样的顺序打

?

注意：如果把数组放在函数外用作外部变量的话可以开到很大，至少10000*10000没问题

?

#include<iostream>
#include <cstring>
using namespace std;

?

intmain()
{
????int casenum,temp;
????char str_1[250],str_2[250];
????cin >> casenum;
????while(casenum--)
????{
????????inta[250]={0},b[250]={0},c[250]={0};
????????cin >> str_1 >>str_2;//以字符串的方式读入大数
????????a[0]=strlen(str_1);//计算数据长度
????????b[0]=strlen(str_2);
????????for(int i=a[0];i>0;i--)//转化数组
????????a[a[0]-i+1]=(int)str_1[i-1]-(int)('0');
????????for(int j=b[0];j>0;j--)
????????b[b[0]-j+1]=(int)str_2[j-1]-(int)('0');

????????if(a[0]>b[0])temp=a[0];
????????else temp=b[0];
????????for(int i=1;i<=temp;i++)
?????????c[i]=a[i]+b[i];//模拟运算
????????for(int j=0;j<=temp+1;j++)
????????if(c[j]>9){c[j+1]+=c[j]/10;c[j]%=10;}//进位
????????c[0]=temp;
????????if(c[temp+1]!=0)c[0]++;
????????for(int k=c[0];k>0;k--)//打印大数
????????cout << c[k];
????????cout << endl;
????}
????return 0;
}

?

大数乘法，基本的输入和输出和大数加法一样

在模拟乘法是用的是累加

核心算法??????for(intj=1;j<=b[0];j++)
?????????????????????{
?????????????????????????c[j+i-1]+=a[i]*b[j];
?????????????????????}
对应的位数累加

?

#include<iostream>
#include <cstring>
using namespace std;

inta[1000],b[1000],c[100000000]; //定义为外部变量

intmain()
{
????int casenum,temp;
????char str_1[1000],str_2[1000];
????cin >> casenum;
????while(casenum--)
????{
????????memset(a,sizeof(a));//初始化为0
???????memset(b,sizeof(b));
????????memset(c,sizeof(c));
????????cin >> str_1 >>str_2;//输入数据
????????a[0]=strlen(str_1);
????????b[0]=strlen(str_2);
????????for(int i=a[0];i>0;i--)
????????a[a[0]-i+1]=(int)str_1[i-1]-(int)('0');
????????for(int j=b[0];j>0;j--)
????????b[b[0]-j+1]=(int)str_2[j-1]-(int)('0');

????????for(inti=1;i<=a[0];i++)//模拟乘法 ??????for(int j=1;j<=b[0];j++) ??????????{ ??????????????c[j+i-1]+=a[i]*b[j]; ??????????????if(j+i>c[0])c[0]=j+i-1; ??????????} ????????temp=c[0]; ????????for(int?j=1;j<=temp+1;j++) ????????if(c[j]>9){c[j+1]+=c[j]/10;c[j]%=10;}//进位 ????????c[0]=temp; ????????if(c[temp+1]!=0)c[0]++; ????????for(int k=c[0];k>0;k--)//打印大数 ????????cout << c[k]; ????????cout << endl; ????} ????return 0; }