【题目链接】

ybt 1307：【例1.3】高精度乘法
ybt 1174：大整数乘法
OpenJudge NOI 1.13 09:大整数乘法

【题目考点】

1. 高精度

考察：高精乘高精
高精度计算讲解

【解题思路】

ybt 1307：【例1.3】高精度乘法：该题中是两个100位的数字相乘，结果可能达到200位。
ybt 1174 / OpenJudge 1.13 09 大整数乘法：该题中是两个200位的数字相乘，结果可能达到400位。
代码中将数字数组长度N设为500，即可满足以上两题。

【题解代码】

解法1：使用数组与函数

#include <bits/stdc++.h>
using namespace std;
#define N 505
void Multiply(int a[], int b[], int r[])//高精乘高精 
{
	int i;
    for(i = 1; i <= a[0]; ++i)
    {
        int c = 0;
        for(int j = 1; j <= b[0]; ++j)
        {
            r[i+j-1] += a[i]*b[j] + c;
            c = r[i+j-1] / 10;
            r[i+j-1] %= 10;
        }
        r[i+b[0]] += c;
    }
    i = a[0] + b[0];//确定数字位数 
    while(r[i] == 0 && i > 1)
        i--;
    r[0] = i;
}
void toNum(char s[], int a[])
{
    a[0] = strlen(s);
	for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0] - i] - '0';
}
void showNum(int a[])
{
    for(int i = a[0]; i >= 1; --i)
        cout << a[i];
}
int main()
{
    int a[N] = {}, b[N] = {}, r[N] = {};
    char s[N];
    cin >> s;
    toNum(s, a);
    cin >> s;
    toNum(s, b);
    Multiply(a, b, r);
    showNum(r);
    return 0;
}

解法2：使用高精度数字类

#include<bits/stdc++.h>
using namespace std;
#define N 505
class HPN
{
private:
	int a[N];
public: 
	HPN()
	{
		memset(a, 0, sizeof(a));
	}
	HPN(char s[])
	{
		memset(a, 0, sizeof(a));
		a[0] = strlen(s);
		for(int i = 1; i <= a[0]; ++i)
	        a[i] = s[a[0] - i] - '0';
	}
	int& operator [] (int i)
	{
		return a[i];
	}
	void setLen(int i)//确定数字位数
	{
		while(a[i] == 0 && i > 1)
	        i--;
	    a[0] = i;
	}
	HPN operator * (HPN &b)
	{
		HPN r;
	    for(int i = 1; i <= a[0]; ++i)
	    {
	        int c = 0;
	        for(int j = 1; j <= b[0]; ++j)
	        {
	            r[i+j-1] += a[i]*b[j] + c;
	            c = r[i+j-1] / 10;
	            r[i+j-1] %= 10;
	        }
	        r[i+b[0]] += c;
	    }
	    r.setLen(a[0] + b[0]);
		return r; 
	}
	void show()
	{
		for(int i = a[0]; i >= 1; --i)
        	cout << a[i];
	}
};
int main()
{
	char s1[N], s2[N];
	cin >> s1 >> s2;
	HPN a(s1), b(s2), r;
	r = a*b;
	r.show();
	return 0;
}

1307：【例1.3】高精度乘法

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 30399     通过数: 10666

【题目描述】

【输入】

【输出】

【输入样例】

36
3

【输出样例】

108

【参考代码】

#include <stdio.h>
#include <string.h>
#define MAXN 10010

char s1[MAXN],s2[MAXN];
int a[MAXN],b[MAXN],c[MAXN];

int main()
{
	int i,j,flaga=1,flagb=1;
	int lena,lenb,lenc,jw; 
	 
	//读入字符串
	scanf("%s %s",s1,s2);
	
	//符号处理，1表示正数，0表示负数
	if(s1[0]=='-')
	{
		flaga=0;
		strcpy(&s1[0],&s1[1]);
	}
	if(s2[0]=='-')
	{
		flagb=0;
		strcpy(&s2[0],&s2[1]);
	}
	
	//送入整数数组
	lena=strlen(s1);
	for(i=0;i<lena;i++)
	{
		a[i]=s1[lena-i-1]-'0';
	}
	lenb=strlen(s2);
	for(i=0;i<lenb;i++)
	{
		b[i]=s2[lenb-i-1]-'0';
	}
	
	//模拟竖式乘法
	for(i=0;i<lena;i++)
	{
		jw=0;  //上一轮计算进位
		for(j=0;j<lenb;j++)
		{
			//交叉乘积
			c[i+j]=a[i]*b[j]+jw+c[i+j]; //当前乘积+上次乘积进位+原数 
			jw=c[i+j]/10;  //处理进位
			c[i+j] %=10;
		}
		c[i+lenb]=jw;   //进位设置 
	}
	
	//删除前导零
    lenc=lena+lenb;
    for(i=lenc-1;i>=0;i--)
	{
        if(c[i]==0 && lenc>1)
            lenc--;
		else
            break;
    }
    
    //逆序打印输出
    for(i=lenc-1;i>=0;i--)
        printf("%d", c[i]);
    printf("\n");
    
	return 0;
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1307

第一次发博客，也不知道讲些什么，就分享一下高精度这一块的吧。

说实话我刚开始学高精度的时候觉得挺难的 ，写了代码之后才感觉其实高精度乘法还是比较简单的，就是代码量稍稍有点大。

接下来进入正题

先上张图

 没错应该看的出来，高精度乘法其实就是一位一位去乘，然后按位存储在数组里面，思路差不多就是这样。

由于位数比较多，我们用字符串来进行输入，处理后按位存到整型数组中。

我们用下标来确定存数组的位置，从图中也可以看出a[i]*b[j]就存在[i + j - 1]的位置上，然后每一位都进行累加（这里的累加是指同一位的累加，如a[2]*b[1]和a[1]*b[2]是存在同一位上的，就是都在c[2]中进行累加），累加完毕后再处理进位，最后倒序输出就可以噜~

听着是不是灰常的简单易懂【手动滑稽】

话不多说，上代码 

#include <iostream>
using namespace std;
int a[1005] , b[1005], c[2005];
string x, y;
int main(){
    cin >> x >> y;
    int a1 = x.size();
    int b1 = y.size();
    int c1 = a1 + b1;
    for(int i = 0; i < a1; i++){
        a[a1 -i -1] = x[i] - '0';//输入第一个数
    }
    for(int i = 0; i < b1; i++){
        b[b1 -i -1] = y[i] - '0';//输入第二个数
    }
     
    for(int i = 0; i < a1; i++){
        for(int j = 0; j < b1; j++){
            c[i + j] += a[i] * b[j];//按位相乘并累加
        }
    }
    int x = 0;
    for(int i = 0; i < c1; i++){//处理进位
        c[i] += x;
        x = c[i]/10;
        c[i] %= 10;
    }
    int k = c1;//两数相乘后的位数不会超过两数位数相加之和，所以c1足够了
    while(c[k]==0 && k > 0){//处理前缀0
        k--;
    }
    for(int i = k; i >= 0; i--){//倒序输出
        cout << c[i];
    }
    return 0;
}

对了，刚才忘说了一点，输出时要处理一下前缀0！！！（希望你们别白嫖了代码就走导致没看到这句话）好吧这句话其实不用我说看了代码就知道