C++實現(xiàn)的大數(shù)相乘算法示例
更新時間：2017年08月11日 08:54:50 作者：葉赫那拉坤
這篇文章主要介紹了C++實現(xiàn)的大數(shù)相乘算法,結合實例形式分析了C++大數(shù)相乘的概念、原理及代碼實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了C++實現(xiàn)的大數(shù)相乘算法。分享給大家供大家參考，具體如下：
昨晚校招筆試，虐的沒臉睡覺，能力太渣了，但我還在碼農的坑里前行，希望早日跳坑，解決衣食住行之憂。
大數(shù)相乘，是指那些相乘結果或是乘數(shù)本身用long long類型都會溢出的數(shù)字，通常這些數(shù)字都通過string類型進行表示，借助于可動態(tài)調整大小的數(shù)據結構（vector,string,deque）模擬實現(xiàn)數(shù)字的乘法操作。對于普通的乘法，我們知道m(xù)位數(shù)和n位數(shù)相乘，最后的結果位數(shù)在區(qū)間內[m+n-1,m+n]。例如34*56，我們通常這么計算：
將3，4分別于6相乘，記錄低位的進位，然后將3，4對5進行相同的操作，知道第二個乘數(shù)的最高位乘完，算法結束。
所以我們可以保存每個位數(shù)的相乘結果，最后統(tǒng)一進位轉換。
#include<iostream>
#include<deque>
#include<sstream>
std::string BigNumMultiply(std::string s1,std::string s2){
//記錄最終結果
std::string res="";
//使用deque是因為出現(xiàn)進位時可以在隊列前插入數(shù)據，效率比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++程序設計有所幫助。
相關文章
這篇文章主要介紹了Cocos2d-x人物動作類實例,本文用大量代碼和圖片講解Cocos2d-x中的動作,代碼中同時包含大量注釋說明,需要的朋友可以參考下2014-09-09
內存管理是至關重要的一個方面,堆和棧是C語言中重要的內存分配方式,本文主要介紹了C/C++的堆棧內存分配的實現(xiàn),詳細的介紹了這兩者在管理方式、性能和使用場景,感興趣的可以了解一下2024-07-07
淺談Windows系統(tǒng)下C語言編程中Glib庫的使用
這篇文章主要介紹了Windows系統(tǒng)下C語言編程中Glib庫的使用,Glib庫在多線程編程中經常可以用到,需要的朋友可以參考下2016-02-02
怎么實現(xiàn)類的成員函數(shù)作為回調函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可2013-10-10
本文主要介紹了C語言動態(tài)內存管理的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細介紹了CMake編譯中的庫文件和頭文件鏈接，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
寧可錯殺一千,也不放過一個,這是布隆過濾器的特點,本文主要介紹了C++布隆過濾器的使用示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-09-09
這篇文章主要為大家詳細介紹了C++實現(xiàn)詞法分析器的相關代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
C++中std::stringstream多類型數(shù)據拼接和提取用法小結
本文主要介紹了C++中std::stringstream多類型數(shù)據拼接和提取用法小結,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-09-09
下面小編就為大家?guī)硪黄钊肜斫鈉++常成員函數(shù)和常對象。小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考，一起跟隨小編過來看看吧2016-05-05