一種C++中大數乘法程序

孔柱新

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

關鍵詞： C++; 大數; string; vector

中圖分類號：TP312? ? ? ? ? 文獻標識碼：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 引言

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

1 乘法原理

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

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

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

⑵ 接下來算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]變為44 后，應留下4，把4 加到a[2]上……最終使得a里的每個元素都是1位數，結果就算出來了，是6345。如表3。

2 string和vector

大數的位數超出了基本數據類型的表示范圍，因此不能夠用基本數據類型來表示。string是C++標準庫的一個重要的部分，主要用于字符串處理。可以使用輸入輸出流方式直接進行string[3]操作，也可以通過文件等手段進行string操作。同時，C++的算法庫對string類也有著很好的支持，并且string類還和c語言的字符串之間有著良好的接口。其[ ]操作符支持對字符的讀寫。利用string來接受鍵盤輸入的任意位數的字符串，這就滿足了大數的任意多位的要求，string默認存儲的是字符串，故需要減去‘0’才能得到真實的數值。

Vector[4]是同一種類型的對象集合，能夠容納許多其他類型相同的元素，因此又被稱為容器。與string相同vector同屬于STL（Standard Template Library，標準模板庫）中的一種自定義的數據類型，可以廣義上認為是數組的增強版。在使用它時，需要包含頭文件vector，#include<vector>，vector容器與數組相比其優點在于它能夠根據需要隨時自動調整自身的大小以便容下所要放入的元素。此外，vector也提供了許多的方法來對自身進行操作。如push_back[5]操作，vector尾部加入一個數據;reserve（）操作則告訴vector容器應該預留多少個元素的存儲空間。vector在容量不足時會足倍的增加容量。insert（）[6] 函數有以下三種用法：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前插入區間[start， end）的所有元素。

3 程序

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

#include <iostream>

#include <vector>

#include <string>

#include<windows.h>

using namespace std;

3.1 是程序的輸入存儲

string str; //字符串

vector<int> num1，num2; //向量數組

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

cin >> str;

cout << endl;

num1.reserve（str.size（））; //預留空間

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

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

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數組c*/

3.2 兩個大數相乘程序

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;//首位數字

result[c]%=10; //第二位數字

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調試成功。如圖1所示。

4 結束語

本文程序利用string字符串來接收鍵盤輸入的大數，然后把所接收的字符串每一位存儲到vector數組中，按照兩數相乘的豎式計算規則進行計算。這期間要用到vector的一些方法。此程序并沒有檢測輸入數據的合法性，如果加入這些，程序將會更加完善。

參考文獻（References）：

[1] 郭煒.新標準C++程序設計教程[M].清華大學出版社，2012

[2] 廖作斌.一種利用C++實現大數相乘的算法分析與設計[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++程序設計語言（特別版）[M].北京：機械工業出版社，2009

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

3147501908242