本文實例講述了C++實現的大數相乘算法。分享給大家供大家參考，具體如下：
昨晚校招筆試，虐的沒臉睡覺，能力太渣了，但我還在碼農的坑里前行，希望早日跳坑，解決衣食住行之憂。
大數相乘，是指那些相乘結果或是乘數本身用long long類型都會溢出的數字，通常這些數字都通過string類型進行表示，借助于可動態調整大小的數據結構（vector,string,deque）模擬實現數字的乘法操作。對于普通的乘法，我們知道m位數和n位數相乘，最后的結果位數在區間內[m+n-1,m+n]。例如34*56，我們通常這么計算：
將3，4分別于6相乘，記錄低位的進位，然后將3，4對5進行相同的操作，知道第二個乘數的最高位乘完，算法結束。
所以我們可以保存每個位數的相乘結果，最后統一進位轉換。
#include<iostream>#include<deque>#include<sstream>std::string BigNumMultiply(std::string s1,std::string s2){ //記錄最終結果 std::string res=""; //使用deque是因為出現進位時可以在隊列前插入數據，效率比vector高，大小設為最小 std::deque<int> vec(s1.size()+s2.size()-1,0); for(int i=0;i<s1.size();++i){ for(int j=0;j<s2.size();++j){ vec[i+j]+=(s1[i]-'0')*(s2[j]-'0');//記錄相乘結果 } } //進位處理 int addflag=0; //倒序遍歷，是因為最左邊的值為最高位，最右邊的值在最低位，進位運算要從低位開始 for(int i=vec.size()-1;i>=0;--i){ int temp=vec[i]+addflag;//當前值加上進位值 vec[i]=temp%10;//當前值 addflag=temp/10;//進位值 } //如果有進位，將進位加到隊列頭部 while(addflag!=0){ int t=addflag%10; vec.push_front(t); addflag/=10; } for(auto c:vec){ std::ostringstream ss; ss<<c; res=res+ss.str(); } return res;}int main(){ std::string str1,str2; while(std::cin>>str1>>str2) { std::cout<<str1<<"*"<<str2<<"="<<std::endl; std::cout<<BigNumMultiply(str1,str2)<<std::endl; } return 0;}希望本文所述對大家C++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
