大数乘法

OJ: 4236

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

(1) i=0, j=0, Ans[i+j]+=A[i]*B[j], Ans[0]>9. Ans[i+j+1]=Ans[1]=Ans[0]/10=2 Ans[0]=Ans[0]%10=1
(2) i=0, j=1, Ans[i+j]+=A[i]*B[j], Ans[1]=Ans[1]+A[0]*B[1]=2+12=14. Ans[2]+=Ans[1]/10=1. Ans[1]=Ans[1]%10=4
(3) i=1, j=0, Ans[i+j]+=A[i]*B[j]，Ans[1]=Ans[1]+A[1]*B[0]=4+35=39. Ans[2]+=Ans[1]/10=4. Ans[1]=9
(4). i=1, j=1, Ans[i+j]+=A[i]*B[j]，Ans[2]=Ans[2]+A[1]*B[1]=4+20=24 . Ans[3]+=Ans[2]/10=2. Ans[2]=Ans[2]%10=4
(5). Ans={1,9,4,2}. 从低位向高位输出，最终得到53*47=2491

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-01-31 05:33:59
 * 最后修改: 2025-03-29 18:23:08
 * 文件描述: 大数乘法
****************************************************************/
#include <string>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1000; 

int A[MAXN], B[MAXN], Ans[MAXN * 2] = {0};
int Len_A, Len_B, Len_Ans;

void Read(int *arr, int &len) {
    string cur;
    cin >> cur;
    len = cur.length();
    for (int i = 0; i < len; ++i) {
        arr[i] = cur[i] - '0';
    }
    reverse(arr, arr + len);
}

int main() {
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    
    Read(A, Len_A);
    Read(B, Len_B);

    Len_Ans = Len_A + Len_B; // 乘积的最大可能位数

    // 乘法运算，直接处理进位到Ans[i+j+1]
    for (int i = 0; i < Len_A; ++i) {
        for (int j = 0; j < Len_B; ++j) {
            Ans[i + j] += A[i] * B[j]; // 计算乘积并累加
            
            // 直接处理进位
            if (Ans[i + j] > 9) {
                Ans[i + j + 1] += Ans[i + j] / 10; // 进位到高位
                Ans[i + j] %= 10; // 保留个位数
            }
        }
    }

    // 去除前导零
    while (Len_Ans > 1 && Ans[Len_Ans - 1] == 0) {
        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

数据结构与算法

大数乘法