C++實(shí)現(xiàn)的大數(shù)相乘算法示例
本文實(shí)例講述了C++實(shí)現(xiàn)的大數(shù)相乘算法。分享給大家供大家參考，具體如下：
昨晚校招筆試，虐的沒(méi)臉?biāo)X(jué)，能力太渣了，但我還在碼農(nóng)的坑里前行，希望早日跳坑，解決衣食住行之憂。
大數(shù)相乘，是指那些相乘結(jié)果或是乘數(shù)本身用long long類型都會(huì)溢出的數(shù)字，通常這些數(shù)字都通過(guò)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)算要從低位開(kāi)始
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)文章
這篇文章主要介紹了Cocos2d-x人物動(dòng)作類實(shí)例,本文用大量代碼和圖片講解Cocos2d-x中的動(dòng)作,代碼中同時(shí)包含大量注釋說(shuō)明,需要的朋友可以參考下2014-09-09
C/C++的堆棧內(nèi)存分配的實(shí)現(xiàn)
內(nèi)存管理是至關(guān)重要的一個(gè)方面,堆和棧是C語(yǔ)言中重要的內(nèi)存分配方式,本文主要介紹了C/C++的堆棧內(nèi)存分配的實(shí)現(xiàn),詳細(xì)的介紹了這兩者在管理方式、性能和使用場(chǎng)景,感興趣的可以了解一下2024-07-07
淺談Windows系統(tǒng)下C語(yǔ)言編程中Glib庫(kù)的使用
這篇文章主要介紹了Windows系統(tǒng)下C語(yǔ)言編程中Glib庫(kù)的使用,Glib庫(kù)在多線程編程中經(jīng)?？梢杂玫?需要的朋友可以參考下2016-02-02
怎么實(shí)現(xiàn)類的成員函數(shù)作為回調(diào)函數(shù)
不使用成員函數(shù)，為了訪問(wèn)類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說(shuō)明為類的友元即可2013-10-10
詳解C語(yǔ)言之動(dòng)態(tài)內(nèi)存管理
本文主要介紹了C語(yǔ)言動(dòng)態(tài)內(nèi)存管理的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細(xì)介紹了CMake編譯中的庫(kù)文件和頭文件鏈接，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
寧可錯(cuò)殺一千,也不放過(guò)一個(gè),這是布隆過(guò)濾器的特點(diǎn),本文主要介紹了C++布隆過(guò)濾器的使用示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)詞法分析器的相關(guān)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié)
本文主要介紹了C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
下面小編就為大家?guī)?lái)一篇深入理解c++常成員函數(shù)和常對(duì)象。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧2016-05-05