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