POJ2389: 大數字乘法算法，poj2389乘法
2014-12-26
大數字乘法算法一般是采用模擬"小學生乘法演算過程”方法。
主要算法思想：
1. 乘數a第i）位與乘數b第j）位數字相乘，並將該乘積結果放到乘積結果數組product的第（i+j-1）位中；
2. 檢查product的第（i+j-1）位中儲存的數字是否超過或等於10，若是，則“取余並且進位”。
細節參考代碼：
![]()
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 void solve(string a,string b){
5 int a_length=a.length();
6 int b_length=b.length();
7 int *arr_a=new int[a_length+1];
8 int *arr_b=new int[b_length+1];
9
10 for(int i=1;i<=a_length;i++){
11 arr_a[i] = a[i-1]-'0';
12 }
13 for(int i=1;i<=b_length;i++){
14 arr_b[i] = b[i-1]-'0';
15 }
16
17 int *product=new int[a_length+b_length];
18 int product_length = a_length+b_length-1;
19 for(int i=0;i<=product_length;i++) product[i]=0;
20
21 for(int i=a_length;i>=1;i--){
22
23 for(int j=b_length;j>=1;j--){
24 int temp = arr_a[i]*arr_b[j];
25 int c = product[i+j-1]+temp;
26 product[i+j-1] = c%10;
27 product[i+j-2] += c/10;
28 }
29 }
30
31
32 if(product[0]!=0) cout<<product[0];
33 for(int i=1;i<=product_length;i++){
34 cout<<product[i];
35 }cout<<endl;
36 }
37 int main(){
38 string a,b;
39 while(cin>>a>>b){
40 solve(a,b);
41 }
42 return 0;
43 }
View Code
