書圈 - 數據結構C++｜實例：POJ2389—大整數乘法運算（附視頻）－鑽石舞台

本文摘自《數據結構在線編程實訓（C++語言）（全程視頻講解版）》

【實戰2.3】POJ2389—大整數乘法運算

時間限制：1000ms，內存限制：65536K。

問題描述：給定兩個至少40位不超過200位的正整數，求它們的乘積。

輸入格式：輸入兩行，每行一個大正整數。

輸出格式：輸出一行數字表示乘積，不包含前導的零。

輸入樣例：

11111111111111

1111111111

輸出樣例：

12345679011110987654321

解：由於輸入的正整數至少40位，不能採用C++的整數類型變量存儲，只能採用字符串存儲。可以將大整數字符串看成若干位構成的，每一位看成一個元素，位與位之間為線性關係，提取各個位並採用vector<int>向量存儲。

例如，a="123"，b="45"，轉換為vector<int>向量x[2..0]={1，2，3}（x[0]放置最低位的數字），y[1..0]={4，5}，求乘積z的過程如圖2.2所示。歸納起來，假設x有m個數字，y有n個數字，z=x×y，z的位數最多為m+n，求z[k]如下：

再從低位到高位處理z，實現進位操作，即若z[i]≥10，求出進位數re=z[i]/10和餘數z[i]%=10，再執行z[i+1]+=re將進位數累加到更高位中。最後輸出z。

■圖2.2 計算123×45的過程

對應的程序如下：

#include<iostream>#include<vector>#include<string>constintMAX=202;usingnamespacestd;voidsolve(string&a,string&b)//求解算法{ vector<int> x(MAX),y(MAX),z(2*MAX+1);intj=0;for(inti=a.length()-1;i>=0;i--) //轉換為位，最低位在x[0] x[j++]=a[i]-'0';j=0;for(inti=b.length()-1;i>=0;i--)y[j++]=b[i]-'0';for(inti=0;i<a.length();i++) //求各位的乘法for(intj=0;j<b.length();j++)z[i+j]+=x[i]*y[j];for(inti=0;i<2*MAX;i++)if(z[i]>=10) //處理進位{ intre=z[i]/10; //進位數z[i]%=10; //餘數z[i+1]+=re; //進位數累加到更高位中}boolflag=false; //用於找最高非0位for(inti=2*MAX;i>=0;i--) //從高位開始{ if(z[i]!=0) flag=true; //找到最高非0位，置flag=trueif(flag==true) cout<< z[i]; //找到最高非0位後輸出各個位的數字}if(flag==false) cout<< "0"; //所有數字均為0，輸出一個0cout<< endl;}intmain(){ stringa,b;cin>> a;cin>> b;solve(a,b);return0;}

上述程序是AC代碼，運行時間為16ms，占用空間為148K，編譯語言為C++。

實例講解

數據結構在線編程實訓（C++語言）

往期回顧

【實戰1.1】POJ1504—求倒數和的倒數

【實戰1.2】HDU2114—求s(n)

【實戰2.1】LeetCode26—刪除排序數組中的重複項

【實戰2.2】LeetCode24—兩兩交換鍊表中的結點

下期預告

【實戰2.4】POJ1208—箱子操作

視頻講解

參考書籍

《數據結構在線編程實訓（C++語言）（全程視頻講解版）》

ISBN：9787302585183

作者：李春葆、匡志強、蔣林

定價：69.8元

內容簡介

本書是《數據結構教程（C++語言描述）》（第2版微課視頻版）（李春葆等編著，清華大學出版社，以下簡稱為《教程》）的配套實戰題和在線編程題實訓指導書，詳細給出了《教程》中所有實戰題和在線編程題的解題思路和參考源代碼，提供了全部題目的講解視頻。書中實戰題和在線編程題不僅涵蓋數據結構課程的基本知識點，還融合了各個知識點的運用和擴展，學習、理解和借鑑這些內容是掌握和提高編程能力的**捷徑。本書自成一體，可以脫離《教程》單獨使用，適合高等院校計算機及相關專業的學生使用。