基于C++实现的大整数计算

Pubertyly

发布日期: 2019-03-12 17:29:55 浏览量: 466
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1、实验题目

大整数(big integer):位数很多的整数,普通的计算机不能直接处理,如:9834975972130802345791023498570345。

对大整数的算术运算,显然常规程序语言是无法直接表示的。编程实现大整数的加、减、乘运算,需考虑操作数为0、负数、任意位等各种情况。

要求利用分治法,时间复杂度不高于O(n2)。

2、设计思路

2.1 概要设计

设a和b分别为两个大整数,它们的位数过长,以致计算机中没有变量可以一次性存下来,所以要对其进行拆分。使用分治算法的思路是:

将a表示为a = a1×10^k + a2,b表示为b = b1×10^j + b2;

其中k是a2的位数,j是b2的位数。也就是把大整数分成了高位和低位,这样,a×b = a1×b1×10^(j+k) + a1×b2×10^k + b1×a2×10^j + a2×b2;

两个大数相乘变成了四个较小的数相乘,四个较小的数可能仍然过大,可以继续分解,直到分解为每个数都是个位数,再进行算数运算,这个过程使用递归。

2.2 详细设计

具体计算时,需要先实现加法和减法,才能实现乘法,而且在算数运算过程中还要用到一些辅助函数。

2.2.1 加法

用字符串存放大整数,在进行运算前,先要判断两个大数的符号:

假如都为负数,则去掉最高位的负号,用绝对值进行加法,最后在结果的最高位恢复负号;如果一正一负,则转换为减法,直接调用大数减法函数;如果两者皆为正数,则继续运算。

加法运算过程不需要递归,将两个字符串从末端开始取字符,转换成数字后进行加法,大于9则进位,最终结果仍以字符串返回。

2.2.2 减法

与加法类似,先判断符号,两个一正一负的两个数相减时,转换成加法,调用加法函数;两个负数相减时,用绝对值相减,最后加上符号。

2.2.3 移位

在前面的分析中,高位的数乘上了一个10的幂次方,在实际运算过程中,通过在字符串末尾增加字符0的方法来实现,所以将这一功能封装为一个移位函数。

2.2.4 对齐

对于计算的两个数的位数不等的情况,在较短的数之前补零使两者等长,这一过程也用函数实现。

2.2.5 乘法

先将两个大数各自拆分成两部分,再递归调用大数乘法函数,将四个小数相乘,相乘的结果再用前面实现的大数加法加起来,得到最后的结果。递归的结束条件是,数字的尾款为0或1。

3、运行演示

在程序中给出了一组测试用例,a = 1234567890,b = 9876543210,运算结果如图2-1,分别输出两数之和、差、积。

继续输入测试用例,a的值不变,b取原值的相反数,测试一正一负的计算,结果如图2-2,可见乘积的绝对值不变,但是多出了负号。

再测试两个负数的计算,a = -1111222233334444, b = -5555666677778888,运算结果如图2-3,乘积为正数。

测试0的运算,a = 0,b任意输入一个值,运算结果如图2-4,两数之和为b,差为-b,乘积为0。

上传的附件 cloud_download 基于C++实现的大整数计算.7z ( 64.67kb, 2次下载 )
error_outline 下载需要5点积分

keyboard_arrow_left上一篇 : 基于C++实现的最优二分查找树 基于C语言实现的最近点对问题 : 下一篇keyboard_arrow_right



Pubertyly
2019-03-12 17:30:17
编程实现大整数的加、减、乘运算,需考虑操作数为0、负数、任意位等各种情况

发送私信

走在一起是缘分,一起在走是幸福

18
文章数
20
评论数
最近文章
eject