高精度算法——乘法篇

小呆树屋 2021-09-07

2405

上一篇我们详细讲解了高精度加法，这一篇我们就详细的讲解一下高精度乘法的用法。

本文会详细讲解高精度乘法运算，演示代码使用C艹进行编写，这个算法有关例题为（https://www.luogu.com.cn/problem/P1303）。

本人水平有限，如果有问题欢迎指出，不吝赐教。

高精度乘法

高精度乘法实质上是在高精度加法上更进一步，具体原理相似。聪明的同学是可以很容易推导出高精度乘法的思路。我们以514*495为例。

与高精度加法类似，在运用高精度乘法时，同样也需要把数字用数组的形式进行储存，这里不再过多强调。

数	第6位	第5位	第4位	第3位	第2位	第1位
a				5	1	4
b				4	9	5
a*b[1]				25	5	20
a*b[2]			45	9	36
a*b[3]		20	4	16
中间产物		20	49	50	41	20
进位结果	2	5	4	4	3	0
结果	2	5	4	4	3	0

仔细观察这个表格，不难看出，a[i]*b[j]的结果全在i+j-1的位置上。利用这个特性，我们可以很方便计算出中间产物的位置，最后在对整个算式进行进位。同高精度加一样，在进位中同样要注重进位的方向。总体而言跟高精度加过程大同小异，也比较简单。

示例代码

#include<bits/stdc++.h>
using namespace std;


int main(){
    string a,b;
    int c[2010]={0},d[2010]={0};
    int e[50001]={0};
    int l1,l2;
    cin>>a>>b;
    l1=a.size();
    l2=b.size();
    for (int i = 1; i <= l1; i++) c[i]=a[l1-i]-'0';
    for (int i = 1; i <= l2; i++) d[i]=b[l2-i]-'0';//转换类型
    for (int i = 1; i <= l1; i++)
    {
        for (int j = 1; j <= l2; j++)
        { 
            e[j+i-1]+=c[i]*d[j]; //计算结果
        }
        
    }
    for (int i = 1; i < l1+l2; i++)
    {
        if(e[i]>=10){
            e[i+1]+=e[i]/10;
            e[i]%=10; // 处理进位
        }
    }
    int len=l1+l2; // 乘法的乘积不超过两数的位数之和
    while (e[len]==0&&len>1) len--; // 去掉前导的0
    for (int i = len; i >= 1; i--)
    {
        cout<<e[i]; // 输出结果
    }
    return 0;
    
}

一如既往的写了python题解



a=input()
b=input()
a=int(a)
b=int(b)
print(a*b)

写的高精度乘法模板

string multiply(string A,string B){
    int a[500]={}, b[500]={},c[500]={0};
    string ans;
    for(int i=1; i<=A.size(); i++) a[i]=A[A.size()-i]-'0';
    for(int i=1; i<=B.size(); i++) b[i]=B[B.size()-i]-'0';
    for(int i=1;i<=A.size();i++){
        for(int j =1;j<=B.size();j++){
            c[i+j-1]+=a[i]*b[j];
        }
    }
    int len=A.size()+B.size();
    for(int i=1;i<=len;i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while (c[len]==0&&len>1) len--;
    for(int i=1; i<=len; i++) ans=char(c[i]+'0')+ans;
    return ans;
}

文章最后祝大家学业有成，不断进步

如果觉得写的好欢迎点个赞

数据库

文章转载自小呆树屋，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

高精度算法——乘法篇

评论