一種C++中大數(shù)乘法程序

孔柱新

摘? 要： 程序模擬了兩數(shù)相乘的人工豎式算法，利用C++標(biāo)準(zhǔn)模板庫中string類接收鍵盤輸入的大數(shù)，并用標(biāo)準(zhǔn)模板庫vector類存儲大數(shù)和相乘，解決了基本數(shù)據(jù)類型表示大數(shù)位數(shù)有限的問題。

關(guān)鍵詞： C++; 大數(shù); string; vector

中圖分類號：TP312? ? ? ? ? 文獻標(biāo)識碼：A? ? ?文章編號：1006-8228（2022）03-81-03

Abstract： The program simulates the artificial vertical calculation method of multiplication of two numbers， using the string class of C++ standard template library to receive the large number of keyboard input. The vector class of standard template library is used to store large numbers and multiply them， which solves the digits limiting problem for the basic data type to represent the large number.

Key words： C++; large number; string; vector

0 引言

隨著科技的發(fā)展，計算機系統(tǒng)的性能越來越高，給人們的工作和生活帶來了便利。雖然是如此，但計算機所能表示的數(shù)據(jù)范圍還是有限制的。C++中l(wèi)ong long的最大值[1]：9223372036854775807，long long的最小值：-9223372036854775808;unsigned long long的最大值：18446744073709551615;大數(shù)超出了計算機系統(tǒng)基本數(shù)據(jù)類型所能表達的范圍，例如有的數(shù)據(jù)可能有成百上千位，如果這樣的數(shù)據(jù)相乘就超出了基本數(shù)據(jù)類型所能表達的范圍。本文探討了一種利用C++程序編寫兩個大整數(shù)相乘的算法，希望起到拋磚引玉的效果。

1 乘法原理

首先看看兩數(shù)相乘的算法[2]，模擬人工計算時的方法，也就是列豎式相乘，從低位向高位乘，在豎式計算中，我們是將乘數(shù)第一位與被乘數(shù)的每一位相乘，記錄結(jié)果之后，用第二位相乘，記錄結(jié)果并且左移一位，以此類推，直到計算完最后一位，再將各項結(jié)果相加，得出最后結(jié)果。為編程方便，并不急于處理進位，而將進位問題留待最后統(tǒng)一處理。

我們以135*47為例來說明計算過程：

⑴ 先算135*7，7*5得到35個1，7*3得到21個10，7*1得到7個100，如表1是存儲結(jié)果的數(shù)組形式。

⑵ 接下來算135*4，4*5得到20個10，4*3得到12個100，4*1得到4個1000，如表2。

⑶ 乘法過程完畢。接下來從a[0]開始向高位逐位處理進位問題。a[0]留下5，把3加到a[1]上，a[1]變?yōu)?4 后，應(yīng)留下4，把4 加到a[2]上……最終使得a里的每個元素都是1位數(shù)，結(jié)果就算出來了，是6345。如表3。

2 string和vector

大數(shù)的位數(shù)超出了基本數(shù)據(jù)類型的表示范圍，因此不能夠用基本數(shù)據(jù)類型來表示。string是C++標(biāo)準(zhǔn)庫的一個重要的部分，主要用于字符串處理?？梢允褂幂斎胼敵隽鞣绞街苯舆M行string[3]操作，也可以通過文件等手段進行string操作。同時，C++的算法庫對string類也有著很好的支持，并且string類還和c語言的字符串之間有著良好的接口。其[ ]操作符支持對字符的讀寫。利用string來接受鍵盤輸入的任意位數(shù)的字符串，這就滿足了大數(shù)的任意多位的要求，string默認存儲的是字符串，故需要減去‘0’才能得到真實的數(shù)值。

Vector[4]是同一種類型的對象集合，能夠容納許多其他類型相同的元素，因此又被稱為容器。與string相同vector同屬于STL（Standard Template Library，標(biāo)準(zhǔn)模板庫）中的一種自定義的數(shù)據(jù)類型，可以廣義上認為是數(shù)組的增強版。在使用它時，需要包含頭文件vector，#include<vector>，vector容器與數(shù)組相比其優(yōu)點在于它能夠根據(jù)需要隨時自動調(diào)整自身的大小以便容下所要放入的元素。此外，vector也提供了許多的方法來對自身進行操作。如push_back[5]操作，vector尾部加入一個數(shù)據(jù);reserve（）操作則告訴vector容器應(yīng)該預(yù)留多少個元素的存儲空間。vector在容量不足時會足倍的增加容量。insert（）[6] 函數(shù)有以下三種用法：iterator insert（ iterator loc， const TYPE &val），在指定位置loc前插入值為val的元素，返回指向這個元素的迭代器;void insert（iterator loc， size_type num， const TYPE &val），在指定位置loc前插入num個值為val的元素;void insert（iterator loc， input_iterator start， input_iterator? end），在指定位置loc前插入?yún)^(qū)間[start， end）的所有元素。

3 程序

下面是程序的一些清單：在程序的開始的地方，嵌入頭文件。

#include <iostream>

#include <vector>

#include <string>

#include<windows.h>

using namespace std;

3.1 是程序的輸入存儲

string str; //字符串

vector<int> num1，num2; //向量數(shù)組

cout << "please input the first number：＼n";

cin >> str;

cout << endl;

num1.reserve（str.size（））; //預(yù)留空間

for （i=0; i<str.size（）; ++i）

{ num1.push_back（str[i] - '0'）; } //存儲數(shù)據(jù)vector數(shù)組

cout << "please input the second number：＼n";

cin >> str;

cout << endl;

num2.reserve（str.size（））;

for （i = 0; i < str.size（）; ++i）

{ num2.push_back（str[i] - '0'）; }

vector<int> num（num1.size（） +num2.size（） - 1， 0）;

/*初始化vector數(shù)組c*/

3.2 兩個大數(shù)相乘程序

void bignumbermultiply（const vector<int> &num1，

const vector<int> &num2， vector<int> &result）

{ int a， b， c;

int tmp;

for （a=0; a<num1.size（）; ++a）

{ c=a;

for （b=0; b< num2.size（）; ++b）

{ result[c++] += num1[a] * num2[b]; }}

for （c=result.size（）-1; c>=0; --c）

{ if （result[c]>9）

{ if （c ！= 0）

{ result[c-1] += result[c]/10; //進位相加

result[c]%=10;}

else{tmp=result[c]/10;//首位數(shù)字

result[c]%=10; //第二位數(shù)字

result.insert（result.begin（），tmp）; }}}}/*插入到首位*/

3.3 輸出顯示程序

for （i=0; i<num.size（）; ++i） { cout << num[i]; }

cout << endl;system（"pause"）; cout << endl;

此程序在Windows10下，VC++2010調(diào)試成功。如圖1所示。

4 結(jié)束語

本文程序利用string字符串來接收鍵盤輸入的大數(shù)，然后把所接收的字符串每一位存儲到vector數(shù)組中，按照兩數(shù)相乘的豎式計算規(guī)則進行計算。這期間要用到vector的一些方法。此程序并沒有檢測輸入數(shù)據(jù)的合法性，如果加入這些，程序?qū)油晟啤?/p>

參考文獻（References）：

[1] 郭煒.新標(biāo)準(zhǔn)C++程序設(shè)計教程[M].清華大學(xué)出版社，2012

[2] 廖作斌.一種利用C++實現(xiàn)大數(shù)相乘的算法分析與設(shè)計[J].科技通報，2012（6）

[3] Stephen Prata.C++ Primer Plus中文版（第六版）[M].北京：人民郵電出版社，2012

[4] Stanley B.Lippman，Josee Lajoie，Barbara E.Moo. C++Primer中文版（第四版）[M].北京：人民郵電出版社，2006

[5] Bjarne Stroustrup C++程序設(shè)計語言（特別版）[M].北京：機械工業(yè)出版社，2009

[6] 鄭莉，董淵.C++語言程序設(shè)計（第四版）[M].北京：清華大學(xué)出版社，2010

3147501908242