大数乘法

高精度乘法的主要步骤：
1、字符串形式读入两个高精度数(因为大数可能很位数很长，所以用字符串)。
2、将两个高精度数按数位拆分后，逆序存储到两个数组中。
3、模拟乘法竖式，枚举两个乘数的每一位分别相乘，将结果统计到积的对应位。
4、从低到位依次处理进位的问题。
5、从高到低依次输出结果。

A=(5*10)+3, B=(4*10+7) , Ans=(5*4*100)+(5*7+3*4)*10+3*7

(1) i=0, j=0, Ans[i+j]+=A[i]*B[j], Ans[0]=Ans[0]+A[0]*B[0]=0+21=21.
(2) i=0, j=1, Ans[i+j]+=A[i]*B[j], Ans[1]=Ans[1]+A[0]*B[1]=0+12=12
(3) i=1, j=0, Ans[i+j]+=A[i]*B[j]，Ans[1]=Ans[1]+A[1]*B[0]=12+35=47.
(4). i=1, j=1, Ans[i+j]+=A[i]*B[j]，Ans[2]=Ans[2]+A[1]*B[1]=0+20=20.
(5). Ans={21,47,20}. 从低位向高位处理进位，最终得到Ans={1,9,4,2}.

代码复制示例

/**************************************************************** 
 * Description: 
 * Author: Alex Li
 * Date: 2024-01-31 05:33:59
 * LastEditTime: 2024-01-31 05:45:38
****************************************************************/
#include 
#include 
using namespace std;

const int MAXN = 1000; // 定义最大长度为1000
int A[MAXN], B[MAXN], Ans[MAXN], Len_A, Len_B, Len_Ans; // 定义两个操作数数组、结果数组及它们的长度

// 读取大数并转换为数组的函数
void Read(int *A, int &Len) {
    string cur;
    cin >> cur; // 读取字符串表示的大数
    Len = cur.length(); // 计算字符串长度
    for (int i = 0; i < Len; ++i) {
        A[i] = cur[i] - 48; // 将每个字符转换为对应的整数，并存入数组
    }
    reverse(A, A + Len); // 反转数组，使低位在数组前端
}

int main() {
    Read(A, Len_A); // 读取并处理第一个大数
    Read(B, Len_B); // 读取并处理第二个大数

    Len_Ans = Len_A + Len_B - 1; // 初始化结果数组长度

    // 进行大数乘法的核心操作
    for (int i = 0; i < Len_A; ++i) {
        for (int j = 0; j < Len_B; ++j) {
            Ans[i + j] += A[i] * B[j]; // 将A的每一位与B的每一位相乘，并累加到结果数组的对应位置
        }
    }

    // 处理进位
    for (int i = 0; i < Len_Ans; ++i) {
        if (Ans[i] > 9) {
            Ans[i + 1] += Ans[i] / 10; // 向高位进位
            Ans[i] %= 10; // 保留当前位的一位数
        }
    }

    // 逆序输出结果，最高位可能有
    if (Ans[Len_Ans] != 0) cout << Ans[Len_Ans];

    for (int k = Len_Ans - 1; k >= 0; --k) {
        cout << Ans[k];
    }
    return 0;
}

方法二：

/**************************************************************** 
 * Description: 大数乘法
 * Author: Alex Li
 * Date: 2023-07-08 17:32:17
 * LastEditTime: 2024-06-11 08:06:58
****************************************************************/
#include <iostream> // 引入输入输出流库
#include <cstring>  // 引入字符串处理库
#include <cstdio>   // 引入C标准输入输出库
using namespace std;

char a1[101], b1[101];  // 定义字符数组，用于存储输入的两个大数字符串
int a[101], b[101], c[10001];  // 定义整型数组，用于存储反转后的数字和结果

int main() {
    int lena, lenb, lenc, i, j, x;  // 定义变量：数字长度及循环控制变量

    // 输入两个大数字符串
    scanf("%s", a1);
    scanf("%s", b1);

    // 获取字符串长度
    lena = strlen(a1);
    lenb = strlen(b1);

    // 将字符串反转并转换为数字存储在数组中，a和b从数组最后一个元素开始存储，即个位
    for (i = 0; i <= lena; i++) a[lena - i] = a1[i] - 48;
    for (i = 0; i <= lenb; i++) b[lenb - i] = b1[i] - 48;

    // 进行大数乘法运算
    for (i = 1; i <= lena; i++) {
        x = 0;  // 用于存储进位
        for (j = 1; j <= lenb; j++) {
            c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];  // 计算当前位置的乘积及进位
            x = c[i + j - 1] / 10;  // 计算新的进位
            c[i + j - 1] %= 10;  // 当前位只保留个位数
        }
        c[i + lenb] = x;  // 最后的位置保存进位
    }

    // 计算结果的实际长度（去掉前导零）
    lenc = lena + lenb;
    while (c[lenc] == 0 && lenc > 1) lenc--;

    // 输出结果
    for (i = lenc; i >= 1; i--) cout << c[i];
    cout << endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

大数乘法