C++ vector 大数乘法_飞蚂蚁哥哥

http://blog.sina.com.cn/u/2729323945

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

C++ vector 大数乘法

(2013-08-23 22:31:13)

标签：

vector

大数乘法

分类：编程算法

from：http://hi.baidu.com/hehui1500/item/6711a09f18590fd91e4271fc

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

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

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

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

 C++ Code 

1
2
3
4
5
6
7
8

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 c(a.size() + b.size() - 1, 0);

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

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

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

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

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <iostream>
#include <vector>
#include <string>
using namespace std;

//vector
void multiply(const vector<int> &a, const vector<int> &b, vector<int> &result);

int main(void)
{
    int i;
    //use string to store the user input
    //user vector to store the integer
    string s;
    vector<int> a, b;
    cout << "please input two bignums: \n";
    cin >> s;
    //reserve places to avoid vector frequent expending
    a.reserve(s.size());
    //get the integer from string
    for (i = 0; i < s.size(); ++i)
    {
        a.push_back(s[i] - '0');
    }

    cin >> s;
    b.reserve(s.size());
    for (i = 0; i < s.size(); ++i)
    {
        b.push_back(s[i] - '0');
    }
    //create the result vector and initialize it with 0
    vector<int> c(a.size() + b.size() - 1, 0);

    multiply(a, b, c);
    //print the result
    for (i = 0; i < c.size(); ++i)
    {
        cout << c[i];
    }
    cout << endl;
    return 0;
}

void multiply(const vector<int> &a, const vector<int> &b, vector<int> &result)
{
    int i, j, k;
    int tmp;

    for (i = 0; i < a.size(); ++i)
    {
        k = i;
        for (j = 0; j < b.size(); ++j)
        {
            result[k++] += a[i] * b[j];
        }
    }

    for (k = result.size() - 1;   k >= 0; --k)
    {
        if (result[k] > 9)
        {
            if (k != 0)
            {

                result[k - 1] += result[k] / 10;
                result[k] %= 10;
            }
            else   //如果是第一项大于9则添加一项于头部
            {
                tmp = result[k] / 10;
                result[k] %= 10;
                result.insert(result.begin(), tmp);
            }
        }
    }
}

-------------------------------------- 老子信了你的邪 --------------------------------------------

好啦，咱们运用该算法解决一个ACM题，woj 1142。

题目：输入n，求2^(n+1)-1，n<1000。

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void multiply(const vector<int> &a, const vector<int> &b, vector<int> &result);

int main(void)
{
    int i, j, n;
    while(cin >> n)
    {
        vector<int> a, b, c;

        a.push_back(1);
        b.push_back(2);

        for(i = 0; i <= n; ++i)
        {
            c.assign(a.size() + b.size() - 1, 0);
            multiply(a, b, c);
            a = c;
        }

        for (i = 0; i < a.size() - 1; ++i)
            cout << a[i];
        cout << c[a.size() - 1] - 1;
        cout << endl;
    }
    return 0;
}

void multiply(const vector<int> &a, const vector<int> &b, vector<int> &result)
{
    int i, j, k;
    int tmp;

    for (i = 0; i < a.size(); ++i)
    {
        k = i;
        for (j = 0; j < b.size(); ++j)
            result[k++] += a[i] * b[j];
    }

    for (k = result.size() - 1;   k >= 0; --k)
    {
        if (result[k] > 9)
        {
            if (k != 0)
            {

                result[k - 1] += result[k] / 10;
                result[k] %= 10;
            }
            else
            {
                tmp = result[k] / 10;
                result[k] %= 10;
                result.insert(result.begin(), tmp);
            }
        }
    }
}

上图，见证大数据的时刻：

2^(3+1)-1 = 15

2^(9+1)-1 = 1023

2^(999+1) = @#%$@#!……

http://s6/mw690/a2ae2da9zx6C5rusE3H65&690vector 大数乘法" TITLE="C++ vector 大数乘法" />

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：素数系列（三）——算法总结：判断一个数是否是素数

后一篇：[转载]中科院一研究生的退学感言

新浪BLOG意见反馈留言板　欢迎批评指正