c++实现大数乘法

** _ 思路 _ **

第i位数乘第j位数,乘积是第i+j位数(从0开始)
如123*456
乘积各位数为
个位 3*6
十位 2*6 + 3*5
百位 2*5 + 1*6 + 3*4
千位 1*5 + 2*4
万位 1*4
然后从后往前,取余更新。

** _ 代码 _ **

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct Node
{
    int d[2009];
    int len;

    Node() {memset(d, 0, sizeof(d));}
    Node(char *s)
    {
        memset(d, 0, sizeof(d));
        int i = 0;
        while(s[i] != '\0')
        {
            d[i] = s[i] - '0';
            ++i;
        }
        len = i;
        for(int i=0,j=len-1; i<j; i++,j--)
            swap(d[i],d[j]);
    }

    Node operator * (const Node &t) const
    {
        Node ans;
        for(int i=0;i<this->len;i++)
        {
            for(int j=0;j<t.len;j++)
            {
                ans.d[i+j] += this->d[i] * t.d[j];
            }
        }
        for(int i=0;i<this->len+t.len;i++)
        {
            ans.d[i+1] += ans.d[i] / 10;
            ans.d[i] %= 10;
        }
        int len = this->len+t.len;
        while(len > 1 && ans.d[len-1] == 0)
            len--;
        ans.len = len;
        return ans;
    }

};

char str[1009];

int main()
{
    scanf("%s",str);
    Node a(str);
    scanf("%s",str);
    Node b(str);
    Node ans = a * b;
    for(int i=ans.len-1; i>=0; i--)
        printf("%d",ans.d[i]);
    printf("\n");
    return 0;
}

Case 1:
4038
5255
21219690

Case 2:
123456
234567
28958703552


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!