C++實現的大數相乘算法示例
更新時間：2017年08月11日 08:54:50 作者：葉赫那拉坤
這篇文章主要介紹了C++實現的大數相乘算法,結合實例形式分析了C++大數相乘的概念、原理及代碼實現技巧,需要的朋友可以參考下
本文實例講述了C++實現的大數相乘算法。分享給大家供大家參考，具體如下：
昨晚校招筆試，虐的沒臉睡覺，能力太渣了，但我還在碼農的坑里前行，希望早日跳坑，解決衣食住行之憂。
大數相乘，是指那些相乘結果或是乘數本身用long long類型都會溢出的數字，通常這些數字都通過string類型進行表示，借助于可動態(tài)調整大小的數據結構（vector,string,deque）模擬實現數字的乘法操作。對于普通的乘法，我們知道m(xù)位數和n位數相乘，最后的結果位數在區(qū)間內[m+n-1,m+n]。例如34*56，我們通常這么計算：
將3，4分別于6相乘，記錄低位的進位，然后將3，4對5進行相同的操作，知道第二個乘數的最高位乘完，算法結束。
所以我們可以保存每個位數的相乘結果，最后統(tǒng)一進位轉換。
#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++程序設計有所幫助。
相關文章
這篇文章主要為大家詳細介紹了如何基于Qt編寫全能播放組件，可以支持ffmpeg2/3/4/5/6/Qt4/5/6，感興趣的小伙伴可以跟隨小編一起學習一下2023-06-06
智能指針用于資源管理，為了保證資源的操作得到順利的執(zhí)行防止資源泄露，因此大多數實現都以noexcept在參數列表后聲明為不拋出異常，這篇文章主要介紹了C++簡單實現shared_ptr的代碼,需要的朋友可以參考下2022-09-09
這篇文章主要介紹了C語言實現輸出各種三角形方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
基類成員的private成員不但對于對象是不可見的，對于派生類也是不可見的，只能被基類成員或者友元訪問2013-09-09
Linux?C/C++?timeout命令實現運行具有時間限制功能
inux?timeout命令的一個屬性是時間限制?？梢詾槿魏蚊钤O置時間限制。如果時間到期，命令將停止執(zhí)行，這篇文章主要介紹了Linux?C/C++?timeout命令實現(運行具有時間限制),需要的朋友可以參考下2023-02-02
這篇文章主要介紹了C++動態(tài)數組類的封裝,很重要的概念,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細介紹了C語言面向對象編程中的封裝，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
本篇文章是對求子數組最大和的解決方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
在C++中mutable關鍵字正如字面意思所示,表示「可變的」之意,一般在以下兩種情況中使用較多,一是修飾類中的變量,用來突破const的限制,二是在Lambda表達式中使用,用來捕獲修改表達式之外的變量值,下面我們就針對這兩種使用場景逐個介紹2023-10-10
C 數組允許定義可存儲相同類型數據項的變量，結構是 C 編程中另一種用戶自定義的可用的數據類型，它允許您存儲不同類型的數據項，結構用于表示一條記錄，假設您想要跟蹤圖書館中書本的動態(tài)，您可能需要跟蹤每本書的下列屬性2021-10-10