一种C++中大数乘法程序

2022-03-21孔柱新

计算机时代 2022年3期

关键词：大数

孔柱新

摘要：程序模拟了两数相乘的人工竖式算法，利用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;