vector、string实现大数加法乘法

理解 vector 是一个容器，是一个数据集，里边装了很多个元素。与数组最大的不同是 vector 可以动态增长。

用 vector 实现大数运算的关键是，以 string 的方式读入一个大数，然后将字串的每一个字符 s[i] 以 int 形式赋给 vector<int> a 中的每一个元素。然后将 a[i] 和 a[j] 加起来（或者乘起来）。每两个元素加起来的结果 <= 18，乘起来的结果 <= 81。

用 string 实现大数加法的方法跟 vector 差不多，但是用 string 做大数乘法就有点麻烦，我写了一会儿没写出来。

1. 用 vector 实现大数加法：

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

//#define min(a,b) ((a>b)?(b):(a))
//#define max(a,b) ((a>b)?(a):(b))
using namespace std;

void bigSum(vector<int> &a, vector<int> &b, vector<int> &sum)
{
    int i, j, k, tmp;
    if( a.size() < b.size() )
    {
        vector<int> vectmp=a;
        a=b;
        b=vectmp;
    }
    
    sum.assign(a.size(), 0);
    for (i=a.size()-1, j=b.size()-1; i>=0; --i)
    {
        if(j>=0) 
        {
            sum[i]=a[i]+b[j];
            j--;
        }
        else sum[i]=a[i];
    }
    
    for (k = sum.size() - 1;   k >= 0; --k)
    {
        if (sum[k] > 9)
        {
            sum[k]-=10;
            if(k!=0) sum[k-1]++;
            else sum.insert(sum.begin(), 1);
        }
    }
}

int main()
{
    string x,y;
    //freopen("in.txt","r",stdin);
    while(cin>>x>>y)
    {
        vector<int> a,b,c;
        for(int i=0; i<x.length(); ++i)
            a.push_back(x[i]-'0');
        for(int i=0; i<y.length(); ++i)
            b.push_back(y[i]-'0');
        
        bigSum(a,b,c);
        for(int i=0; i<c.size(); ++i)
            cout<<c[i];
        cout<<endl<<endl;
    }
    return 0;
}

运行：

2. string 实现大数加法：

//this algorithm is from "oj-killer" of code.google.com
#include <iostream>
#include <cstdlib>     //freopen
#include <string>    //string

using namespace std;
string Sum(string a,string b)
{
    if(a.length()<b.length())
    {
        string temp=a; a=b; b=temp;
    }
    int i,j;
    for(i=a.length()-1,j=b.length()-1;i>=0;i--,j--)
    {
        a[i]=(a[i]+(j>=0?b[j]-'0':0));
        if(a[i]>'9')
        {
            a[i] -=10;
            if(i) a[i-1]++;
            else a='1'+a;
        }
    }
    return a;
}
int main()
{
    string s1,s2;
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(cin>>s1>>s2)
    {
        cout<<"s1:	"<<s1<<endl<<"s2:	"<<s2<<endl;
        cout<<"Sum:	"<<Sum(s1,s2)<<endl<<endl;
    }
    return 0;
}

运行：

3. vector 实现大数乘法：

输入：n

输出：2^(n+1)-1

该算法来自：http://hi.baidu.com/hehui1500/item/6711a09f18590fd91e4271fc

#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);
            }
        }
    }
}

运行：