[高精度乘法]【藍橋 算法提高 高精度乘法】模拟乘法 圖解 例題

【藍橋】例題

http://lx.lanqiao.cn/problem.page?gpid=T311

高精度乘法

http://lx.lanqiao.cn/problem.page?gpid=T70

高精度加法

一、為什麼要高精度？

題目要求乘法加法的數值過大，超出範圍，不能正常計算，是以需要把數字存在數組，每一個元素當成數字的每一位，模拟計算的過程。

二、高精度乘法圖解及分析

1.把數字塞進數組後豎式乘法就可以發現 規律 C[i+j] = a[i]+c[i]

2.但我們會發現數字相乘會存在進位，是以我們得反着存，是以在數組中是這樣的

3 由于前面是反着存的是以輸出需要從後往前輸出

三 具體實作步驟

1 将資料存進字元串中

2 将字元串反轉并存在數組裡

string a1;
	string b1;
	int a[10000],b[10000];
	cin>>a1,cin>>b1;
	for(int i = a1.length()-1,k=0;i>=0;i--){
		a[i] = a1[k++]-'0';
	}
	for(int i = b1.length()-1,k=0;i>=0;i--){
		b[i] = b1[k++]-'0';
	}  
           

3 模拟乘法（注意進位問題）

for(int i = 0;i<a1.length();i++){
    	for(int j = 0;j<b1.length();j++){
			A[i+j] += a[i]*b[j];
			A[i+j+1] += A[i+j]/10;
			A[i+j]%=10;
		}
	}
           

4 删除前導0，并且反向輸出

int len = a1.length()+b1.length();
	while(A[len]==0&&len>0) len--;
	for(int i = len;i>=0;i--){
		cout<<A[i];
	}
           

四 完整代碼

#include<bits/stdc++.h>
using namespace std;
int A[100000001]={0}; // 答案
int main(){
	string a1;
	string b1;
	int a[10000],b[10000];
	cin>>a1,cin>>b1;
	for(int i = a1.length()-1,k=0;i>=0;i--){
		a[i] = a1[k++]-'0';
	}
	for(int i = b1.length()-1,k=0;i>=0;i--){
		b[i] = b1[k++]-'0';
	}    // 反轉存儲
//	cout<<a[0]<<" "<<a[1];
	
    for(int i = 0;i<a1.length();i++){
    	for(int j = 0;j<b1.length();j++){
			A[i+j] += a[i]*b[j];
			A[i+j+1] += A[i+j]/10;
			A[i+j]%=10;
		}
	}
	int len = a1.length()+b1.length();
	while(A[len]==0&&len>0) len--;
	for(int i = len;i>=0;i--){
		cout<<A[i];
	}
	return 0;
}
           

附加 高精度加法

總體而言差不多 差別在于模拟加法和位數控制不一樣

#include<bits/stdc++.h>
using namespace std;
int ans[1000000]={0};
int main(){
	string a1,b1;
	cin>>a1>>b1;
	int a[10000],b[10000];
	for(int i = a1.length()-1,k=0;i>=0;i--){
		a[i] = a1[k++]-'0';
	}
	for(int i = b1.length()-1,k=0;i>=0;i--){
		b[i] = b1[k++]-'0';
	}    // 反轉存儲
	for(int i = 0;i<a1.length()||i<b1.length();i++){
		ans[i] += a[i]+b[i];
		ans[i+1]+=ans[i]/10;
		ans[i] %=10;
	//	cout<<ans[i]<<endl;
	}
	int len = max(a1.length(),b1.length())+1;
	while(ans[len]==0)len--;
	for(int i = len;i>=0;i--){
		cout<<ans[i];
	}
	return 0;
}