大数(加、减、乘、除、低精度*大数)模板详解（C++）

一、大数四个基本操作

首先，我们来了解什么是大数，大数就是指用我们平常常见的高级语言（如：c、c++）的基本数据类型的最大长度都装不下的数据，例如（1234567899876543211234567896542132165465），这些只能用字符数组（char[]）或者字符串（string）来处理，大数操作最基础的四个操作就是：大数加法、大数减法、大数乘法、大数除法。下面我来详细介绍下四个基础操作的算法。

在介绍算法之前，先了解一下几个C++中 string数据类型的用法。因为string类字符元素的访问比C字符串有所增强，优点十分多，用起来很方便，所以下面我大数模板全部是基于string来作为基础数据类型。

String 优点如下（相对C）

1）string可以像C的字符串数组一样用下标来直接访问索引值对于的字符。

string str=”123456789123123” //初始化一个字符串

str[i]                 //返回str中索引i处字符的引用，不查是否出界

str.at(i)              //返回str中索引i处字符的引用，查是否出界

2）string重载了一些运算符，特别注意当目标串较小，无法容纳新的字符串，系统会自动分配更多的空间给目标串，不必顾虑出界：

3）string字符串之间的赋值不再需要像C那样移动数组或者用strcpy()等函数辅助，string类可以直接赋值：

str1=str2;                     //str1成为str2的代码

str1+=str2;                    //str2的字符数据连接到str1的尾部

str1+str2;                //返回一个字符串，它将str2和str1连接起来

4）string字符串之间的比较也不需要用strcmp()等函数来比较，可以直接用<>==

str1==str2; str1!=str2;       //比较串是否相等，返回布尔值

str1<str2;  str1>str2;         //基于字典序的比较，返回布尔值

str1<=str2;  str1>=str2;

5) string字符串还有一个标准且强大的STL库，里面提供了许多非常便利有用的辅助函数，如 str. erase ()函数（详细介绍这个，因为下面算法经常利用到）

erase函数的原型如下：（1）string& erase ( size_tpos = 0, size_t n = npos );(常用)

     作用：从下标size_t pos开始，去掉size_t n个字符

     例子：str=”023543”

     用法：str.erase(0,1);

     结果：str=“23543”（2）iterator erase ( iteratorposition );

     作用：去掉一个下标为：position的字符

     例子：str=”023543”

     用法：str.erase(0);

     结果：str=“23543”（3）iterator erase ( iteratorfirst, iterator last );

作用：删除从first到last之间的字符（first和last都是迭代器）

好了，了解string到这里也差不多了。接下来就是算法分析

一、大数加法

原理：首先我们要对字符串进行初始化处理，就是给它们前面补上一个‘0’，防止有进位，如果没有进位我们最后可以用erase()函数将其删掉，然后直接对字符串进行操作，从字符串尾开始操作，往回对应相加，如果相加的结果>10，那么前一个字符就要加上当前字符的进位，当前字符就只保留结果个位数

下面是图解：

代码如下

二、大数减法

原理：减法操作和加法操作类似，首先先初始化，保持输入都是大数减小数，然后从低位开始对应相减，不够减就从借位减一。

代码如下

三、大数乘法

原理：乘法的主要思想是把乘法转化为加法进行运算。

例子（12345*24）首先用相对小的大数（24）作为循环分割，4和 20，个位数4代表着4个123456相加。

        12345*4=12345+12345+12345+12345

20代表着20个12345相加，也就是2个123450相加

        12345*20=123450+123450

最终结果就是4个12345加上2个123450

        12345*24=12345+12345+12345+12345+123450+123450

代码如下：

                                                                                        不明白?

我带大家走一遍Debug，看一下数据的变化

首先初始化:

循环加上4次加上12345后结果res=49380

重复，循环2次加上123450，res=296280

最终结果

四、大数除法

原理：首先想到的是运用大数减法，例如144 / 12，就是循环利用大数减法144-12,减一次就用大数加法加1，最终结束循环的条件是被减数小于减数。这个方法实现起来简单，逻辑直观，但是效率明显不够高，不信可以试一试（978973548932486564654654654654654654654564564564654532165454654 /2）

这个运用上面的方法会编译器会直接卡死。其实呢，上面的只要进行优化一下就可以AC了。怎么优化呢？

这样，首先我们可以直接将减数扩展到刚刚好比被减数少一位（用‘0’扩展，就是乘于10,例如这里刚好是扩大10倍）然后再大数相减，减一次就用大数加法加起来（这里是加10），循环操作，同样，循环结束条件也是被减数小于减数,这样可以避免循环减一个小数的尴尬。

代码:

                                                                                        不明白?

下面走一遍debug，看一下数据变化

测试样例（9090901 / 9）

第一步：扩展减数，在这里减数从9扩展为900000，相当于*100000

第二步：接着循环相减直至被减数小于扩展的减数即(a<tmp)结束，此时也循环大数相加加上了对应的扩展倍数就是结果（res）

由于被减数(a=90901)还是大于减数（b=9），循环继续

此时被减数(a=90901)小于扩展的除数（tmp=900000）了，需要将扩展的除数变小（这里将它缩小10倍，即tmp=90000）图如下：

然后重复第二步的操作，直至被减数小于减数即(a<b)结束。

最终结果:

二、低精度*大数：

     低精度*大数例如阶乘（N！），1000！将会是一个非常大的数，用我们的基本数据类型是无法装下的，1*2*3*4*·······*10000

当然这利用我们前一小节所说的大数乘法完成该功能也可以，但是还有一种专门用来处理这种情况的方法，就是利用一个数组来保存每一位的字符。

例如：

5的阶乘在数组里面就是：

6的阶乘在数组里面就是：

7的阶乘在数组里面就是：

发现吗？

数组的第一个元素其实就是表示当前结果的位数，其他元素就是结果的每一位数

5！=120

6！=720

7！=5040

那其中是如何实现的呢

代码如下:

首先使用一个数组num[50000]来存储结果，将其初始化为0，num[0]=1，num[1]=1

这里设定num[1]=1是因为阶乘的原因，因为0的阶乘还是1；

文字表达水平有限，原理还是看我debug走一遍更好理解

测试样例是6的阶乘（测试样例太大不好讲解）

做好初始化工作：i=1;                                [结果]res=1

第一步判断num[0]此时的结果有多少位，再循环分别每位乘以i(第一轮i=1)

循环后数组没有变化

第二轮循环开始：i此时为2 res*2[注意，这里*2是指结果的每一位乘以2]res=2

数组变化

第三轮循环开始：i=3,res*3

数组变化

第四轮循环开始: i=4，res*4

注意这里出现了24,没错，就是6*4=24，24>10了，此时就要进位，向后进位，原位置保持个位数，num[0]就要加多一位了，代表这结果的位数

数组变化

第五轮循环开始: i=5，res*5

每位分别乘以5,4*5=20 2*5=10

再循环分割进位

数组变化

第六轮循环开始: i=6，res*6

同样，每一位都分别乘以6

即：0*6=0 2*6 =12 1*6=6

扫描有大于10的进行进位拆分

数组变化

结束循环

最终：模板代码如下

#include<cstdio>#include<iostream>#include<cstring>using namespace std;//初始化 void initial(string &a, string &b){	while (a.size()<b.size())a = '0' + a;	while (b.size()<a.size())b = '0' + b;}//打印 void PRint(string &a, string &b){	cout << a << endl;	cout << b << endl;}//找出最大的字符串 void findMax(string &a, string &b){	string tmp;	if (a<b){		tmp = b;		b = a;		a = tmp;	}}//删除第一个字符'0' bool del(string &a){	if (a[0] == '0'){		a.erase(0, 1);		return true;	}	else		return false;}//删除前面所有的 0 void delAllZroe(string &a){	while (del(a)){		del(a);	};}//大数加法 string bigItergeAdd(string a, string b){	initial(a, b);	a = '0' + a;	b = '0' + b;	for (int i = a.size() - 1; i >= 0; i--){		int num1 = a[i] - '0';		int num2 = b[i] - '0';		if (num1 + num2>9){			a[i - 1] = a[i - 1] - '0' + 1 + '0';			a[i] = (num1 + num2) - 10 + '0';		}		else{			a[i] = (num1 + num2) + '0';		}	}	del(a);	//	cout<<a<<endl;	return a;}//大数减法 string bigItergeSub(string a, string b){	initial(a, b);	findMax(a, b);	for (int i = a.size() - 1; i >= 0; i--){		int num1 = a[i] - '0';		int num2 = b[i] - '0';		if (num1<num2){			a[i - 1] = a[i - 1] - '0' - 1 + '0';			a[i] = (num1 + 10 - num2) + '0';		}		else{			a[i] = (num1 - num2) + '0';		}	}	del(a);	//	cout<<a<<endl;	return a;}//大数乘法(大数加法实现) void bigItergeMul(string a, string b){	delAllZroe(a);	delAllZroe(b);	if (a == "" || b == ""){ printf("0/n"); return; }	initial(a, b);	findMax(a, b);	string res = "0";	int count = 0;	delAllZroe(b);	for (int i = b.size() - 1; i >= 0; i--){		int num1 = b[i] - '0';		if (i != b.size() - 1)		a = a + '0';		for (int i = 1; i <= num1; i++){			res = bigItergeAdd(res, a);		}	}	delAllZroe(res);	cout << res << endl;}//大数除法 void bigItergeDiv(string a, string b){	initial(a, b);	if (a<b){ cout << "0" << endl;	return; }	delAllZroe(b);	string res = "0";	string restmp = "1";	string tmp = b;	for (int i = 1; i<(a.size() - b.size()); i++){		tmp += '0';		restmp += '0';	}	initial(a, b);	while (a >= b){		initial(a, tmp);		if (a >= tmp){			a = bigItergeSub(a, tmp);			res = bigItergeAdd(res, restmp);		}		else{			tmp.erase(tmp.size() - 1);			restmp.erase(restmp.size() - 1);			initial(a, tmp);			if (a >= tmp){				a = bigItergeSub(a, tmp);				res = bigItergeAdd(res, restmp);			}		}		initial(a, b);	}	cout << res << endl;}//阶乘（0~10000）【实际是低精度 乘于(*) 大数 例如：1000 *32132156465465321】 void factorial(int n){	int num[50000];	memset(num, 0, sizeof(num));	num[0] = 1;	num[1] = 1;	for (int i = 1; i <= n; i++){		int len = num[0];		for (int j = 1; j <= len; j++){			num[j] *= i;		}		for (int j = 1; j <= num[0]; j++){			if (num[j]>9){				num[j + 1] += num[j] / 10;				num[j] %= 10;			}			if (num[num[0] + 1] != 0)num[0]++;		}	}	for (int i = num[0]; i>0; i--){		printf("%d", num[i]);	}	printf("/n");}int main(){	string a, b;	while (cin >> a >> b){//		bigItergeAdd(a,b);//		bigItergeSub(a,b);		bigItergeMul(a,b);	//		bigItergeDiv(a, b);	}//	int n;//	while(scanf("%d",&n)!=EOF){//		factorial(n);//	}	return 0;}
以上的模板已经在acm.hdu.edu.cn和openjudge.cn上测试AC
大数加法
http://acm.hdu.edu.cn/showproblem.php?pid=1002
http://bailian.openjudge.cn/practice/1000/
http://acm.hdu.edu.cn/showproblem.php?pid=1047
http://acm.hdu.edu.cn/showproblem.php?pid=1313
 
这题在输入做了手脚，输入0，也要输出0，WA了好几次
大数减法
http://bailian.openjudge.cn/practice/2736/
 
大数乘法
http://bailian.openjudge.cn/practice/2980/
这道题目特坑，竟然在输入做手脚，测试样例会输入一串00000000000000
或者000000000001 * 000000000000001等等，在这上面WA了好几次
 
大数除法
http://bailian.openjudge.cn/practice/2737/
 
低精度*大数（N！）阶乘
http://acm.hdu.edu.cn/showproblem.php?pid=1042
 
这些都是一些非常基础的题目，一眼就看出是大数的运用，但实际运用上，大数只是作为解题的一个桥段，作为一个契机，例如前一篇文章
sicily1029Rabbit 中大OJ解题报告
http://blog.csdn.net/wjb820728252/article/details/60583288