大数乘法

本文摘自www.csdn.net?的PinkRobin的博文，自勉并献于大家，以共享！

近期学习STL，愈发感觉C++之博大精深。一个vector就包含着诸多内容。而语言只是工具，学习语言目的是为了解决问题。近期又是一年复试时，而复试上机有许多学校考察了大数运算方面的知识，例如大数加法、大数乘法和间接考察相关知识的大数阶乘。在学习vector时，突然发现用vector可以很方便的实现大数乘法。

?????? 关于大数乘法，可以使用数组、字符串string等容器来存储数据，而具体的实现则虽随底层容器不同而有所不用，但是大体思想一致：用一个理论上能存储任意多的容器来存储数据，然后利用容器的基本操作来实现大数乘法。使用vector，利用其操作，可以很容易的实现该问题。

?????? 首先可以使用字符串来存储用户的输入，然后把用户输入存储到vector中。具体代码如下：

string s;

?????? vector<int> a,b;

cin >> s;

a.reserve(s.size());

for (i = 0; i < s.size(); ++i)

{

?????? a.push_back(s[i] - '0');

}

这里，应为string默认存储的是字符串，故需要减去‘0’才能得到真实的数值。使用了a.reserve()方法来预留一定的空间是为了提高效率，避免vector容量频繁的扩增。vector在容量不足时会足倍的增加容量，默认是1，依次是：1，2，4，8等等。如果数据较大则会影响效率。

此时需要注意，reserve方法只是预留了空间，并没有改变vector的size()。

在获取了用户的输入后，可以创建用于存储结构的vector。

vector<int> c(a.size() + b.size() - 1,0);

这里把c的大小设置为乘法结果可能的大小，并初始化为0。两个数字相乘，大小是两个数字位数之和减一或者就是两个数字位数之和。这里设置为减一，若不足则最后会在头部插入一位。

有了数据的载体，即可进行大数的乘法运算。具体过程比较简单，不再累述。

该版本可以很简单的改造为数组版本。

注意：如果用数组实现，最好是数字的C[0],不用，最后用于存放进位数，这样就不用移动后面的数字

代码如下(环境VC++6.0)：

1. /**
2. *?? 大数乘法

1. */??
2. ##include "stdafx.h"?? // in vc++6.0
3. #include <iostream> ??
4. #include <vector> ??
5. #include <string> ??
6. using namespace std; ??
7. ??
8. //vector ??
9. void multiply(const vector<int>& a,const vector<int>& b,vector<int>& result); ??
10. ??
11. int main(void) ??
12. { ??
13. ????int i; ??
14. ????//use string to store the user input ??
15. ????//user vector to store the integer ??
16. ???? string s; ??
17. ???? vector<int> a,b; ??
18. ???? cout << "please input two bignums: n"; ??
19. ???? cin >> s; ??
20. ????//reserve places to avoid vector frequent expending ??
21. ???? a.reserve(s.size()); ??
22. ????//get the integer from string ??
23. ????for (i = 0; i < s.size(); ++i) ??
24. ???? { ??
25. ???????? a.push_back(s[i] - '0'); ??
26. ???? } ??
27. ??
28. ???? cin >> s; ??
29. ???? b.reserve(s.size()); ??
30. ????for (i = 0; i < s.size(); ++i) ??
31. ???? { ??
32. ???????? b.push_back(s[i] - '0'); ??
33. ???? } ??
34. ????//create the result vector and initialize it with 0 ??
35. ???? vector<int> c(a.size() + b.size() - 1,0); ??
36. ??
37. ???? multiply(a,b,c); ??
38. ????//print the result ??
39. ????for (i = 0; i < c.size(); ++i) ??
40. ???? { ??
41. ???????? cout << c[i]; ??
42. ???? } ??
43. ???? cout <<endl; ??
44. ????return 0; ??
45. } ??
46. ??
47. void multiply(const vector<int>& a,vector<int>& result) ??
48. { ??
49. ????int i,j,k; ??
50. ????int tmp; ??
51. ??
52. ????for (i = 0; i < a.size(); ++i) ??
53. ???? { ??
54. ???????? k = i; ??
55. ????????for (j = 0; j < b.size(); ++j) ??
56. ???????? { ??
57. ???????????? result[k++] += a[i] * b[j]; ??
58. ???????? } ??
59. ???? } ??
60. ???? ??
61. ????for (k = result.size() - 1;?? k >= 0; --k) ??
62. ???? { ??
63. ????????if (result[k] > 9) ??
64. ???????? { ??
65. ????????????if (k != 0) ??
66. ???????????? { ??
67. ???????????????? ??
68. ???????????????? result[k-1] += result[k] / 10; ??
69. ???????????????? result[k] %= 10; ??
70. ???????????? } ??
71. ????????????else???//如果是第一项大于9则添加一项于头部 ??
72. ???????????? {??? ??
73. ???????????????? tmp = result[k] / 10; ??
74. ???????????????? result[k] %=10; ??
75. ???????????????? result.insert(result.begin(),tmp); ??
76. ???????????? } ??
77. ???????? } ??
78. ???? } ??
79. } ?