高精度乘法

高精度乘法关键代码

//乘法进位：
c[i+j-1]= a[i]*b[j] + x + c[i+j-1];
x = c[i+j-1]/10;
c[i+j-1] %= 10;

高精度乘法。输入两个正整数，求它们的积。

分析

类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加，如图3、图4。
　　分析c数组下标的变化规律，可以写出如下关系式：ci = c’i +c”i +…由此可见，c i跟a[i]b[j]乘积有关，跟上次的进位有关，还跟原c i的值有关，分析下标规律，有c[i+j-1]= a[i]b[j]+ x + c[i+j-1]; x=c[i+j-1]/10 ; c[i+j-1]%=10;

img3.png

img4.png

详细算法如下

#include<iostream>
#include<cstring>
using namespace std;
char a[100]={}, b[100]={};
int a1[100]= {}, a2[100]={}, a3[100]={},la, lb;
int main(){
    cin >> a >>b;
    la = strlen(a);
    lb = strlen(b);
    for (int i = 0; i <= la - 1; i ++){
        a1[la -i] = a[i] - '0';
    }
    for (int i =0; i <= lb- 1; i++){
        a2[lb -i] = b[i] - '0';
    }
    // 做乘法运算
    for (int i = 1; i <= la; i++){  // 乘数 
        int x = 0;
        for (int j = 1;  j<= lb; j++){  // 被乘数 
            a3[i +j -1] = a1[i] * a2[j] + x + a3[i + j - 1];
            x = a3[i + j -1] /10; // 进位
            a3[i+j-1] %= 10; 
        } 
        a3[i+lb] = x; // 最高位的进位 
    } 
    int lc = la + lb;
    while (a3[lc] == 0 && lc >1){ // 去掉多余的0 
        lc--;
    }
    for(int i = lc; i>0; i--){
        cout << a3[i];
    } 
    return 0;
}