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