探索信息学奥赛之路：基础算法-高精度乘法

大家好，欢迎来到IT知识分享网。

【题目描述】

输入两个高精度正整数M和N（M和N均小于100位）。求这两个高精度数的积。

【输入】

输入两个高精度正整数M和N。

【输出】

求这两个高精度数的积。

【输入样例】

36 3

【输出样例】

108

解题思路

用竖式求乘法时，我们观察一下计算的规律。在做乘法运算时，同样有进位，同时对每一位进行乘法运算时，必须进行错位相加（此时可以关注一下，每一位乘法结果与被乘数、乘数指定位数存在什么样的关系）。

竖式乘积计算

分析C数组下标的变化规律，可以写出如下关系式：，由此可见，跟a[i]*b[j]乘积有关，跟上次的进位（carry）有关，还跟原的值有关。

分析下标规律，有：

c[i+j-1] = a[i]*b[j] + carry + c[i+j-1];

carry = c[i+j-1] / 10;

c[i+j-1] %= 10;

参考答案

#include<iostream> using namespace std; int main() { string M,N; cin >> M >> N; int mLen=M.length(),nLen=N.length(); int m[100],n[100],result[10001]; //输入的M,N是高位在左，低位在右 //下面将M,N做反转处理，将低位放到数组的低位，高位放到数组的高位，方便后继for循环处理 for(int i=0; i < mLen; i++) { m[mLen - i]= M[i] - '0'; } for(int i=0; i < nLen; i++) { n[nLen - i]= N[i] - '0'; } for(int i=1; i <= mLen; i++){ //用于存放上次乘积进位 int carry=0; //对乘数的每一位进行处理 for(int j=1; j <= nLen; j++){ //当前乘积+上次乘积进位+原数 result[i + j - 1] = m[i] * n[j] + carry + result[i + j - 1]; //计算本次乘积的进位 carry = result[i + j - 1] / 10; //当前计算结果存入结果数组指定位 result[i + j - 1] %= 10; } //乘数执行完一次循环后，如果有进位，需要教carry写入i+nLen位置(这一步想不明白的话，可以手动列竖式，按照乘法验算一遍看看) result[i + nLen] = carry; } int rLen = mLen + nLen; while(result[rLen] == 0 && rLen > 1) { rLen--; } //倒序输出结果数组 for(int i = rLen; i >= 1; i--) { cout << result[i]; } return 0; }