C++實現(xiàn)的大數(shù)相乘算法示例

更新時間：2017年08月11日 08:54:50 作者：葉赫那拉坤

這篇文章主要介紹了C++實現(xiàn)的大數(shù)相乘算法,結(jié)合實例形式分析了C++大數(shù)相乘的概念、原理及代碼實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了C++實現(xiàn)的大數(shù)相乘算法。分享給大家供大家參考，具體如下：

昨晚校招筆試，虐的沒臉睡覺，能力太渣了，但我還在碼農(nóng)的坑里前行，希望早日跳坑，解決衣食住行之憂。

大數(shù)相乘，是指那些相乘結(jié)果或是乘數(shù)本身用long long類型都會溢出的數(shù)字，通常這些數(shù)字都通過string類型進行表示，借助于可動態(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相乘，記錄低位的進位，然后將3，4對5進行相同的操作，知道第二個乘數(shù)的最高位乘完，算法結(jié)束。

所以我們可以保存每個位數(shù)的相乘結(jié)果，最后統(tǒng)一進位轉(zhuǎn)換。

#include<iostream>
#include<deque>
#include<sstream>
std::string BigNumMultiply(std::string s1,std::string s2){
 //記錄最終結(jié)果
 std::string res="";
 //使用deque是因為出現(xià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é)果
  }
 }
 //進位處理
 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++程序設(shè)計有所幫助。

您可能感興趣的文章:

C++
算法

相關(guān)文章

Cocos2d-x人物動作類實例
這篇文章主要介紹了Cocos2d-x人物動作類實例,本文用大量代碼和圖片講解Cocos2d-x中的動作,代碼中同時包含大量注釋說明,需要的朋友可以參考下
2014-09-09
C/C++的堆棧內(nèi)存分配的實現(xiàn)
內(nèi)存管理是至關(guān)重要的一個方面,堆和棧是C語言中重要的內(nèi)存分配方式,本文主要介紹了C/C++的堆棧內(nèi)存分配的實現(xiàn),詳細的介紹了這兩者在管理方式、性能和使用場景,感興趣的可以了解一下
2024-07-07
淺談Windows系統(tǒng)下C語言編程中Glib庫的使用
這篇文章主要介紹了Windows系統(tǒng)下C語言編程中Glib庫的使用,Glib庫在多線程編程中經(jīng)?？梢杂玫?需要的朋友可以參考下
2016-02-02
怎么實現(xiàn)類的成員函數(shù)作為回調(diào)函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可
2013-10-10
詳解C語言之動態(tài)內(nèi)存管理
本文主要介紹了C語言動態(tài)內(nèi)存管理的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-11-11
CMake編譯中的庫文件和頭文件鏈接你了解嗎
這篇文章主要為大家詳細介紹了CMake編譯中的庫文件和頭文件鏈接，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-02-02
C++布隆過濾器的使用示例
寧可錯殺一千,也不放過一個,這是布隆過濾器的特點,本文主要介紹了C++布隆過濾器的使用示例,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
2023-09-09
C++實現(xiàn)詞法分析器
這篇文章主要為大家詳細介紹了C++實現(xiàn)詞法分析器的相關(guān)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-01-01
C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié)
本文主要介紹了C++中std::stringstream多類型數(shù)據(jù)拼接和提取用法小結(jié),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
2023-09-09
深入理解c++常成員函數(shù)和常對象
下面小編就為大家?guī)硪黄钊肜斫鈉++常成員函數(shù)和常對象。小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考，一起跟隨小編過來看看吧
2016-05-05