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

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

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,分别输出两数之和、差、积。


ac4e7e52e881fd2a2e297d111b336507.jpg

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

10612d206ec9ed1164ff85518b692582.jpg


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

77b8e0962329122e7372beefd022d26b.jpg


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

21fe2f46d5d71ae4ae663fd4f1363994.jpg

目录
打赏
0
0
0
0
29
分享
相关文章
【C++面向对象——类的多态性与虚函数】计算图像面积(头歌实践教学平台习题)【合集】
本任务要求设计一个矩形类、圆形类和图形基类,计算并输出相应图形面积。相关知识点包括纯虚函数和抽象类的使用。 **目录:** - 任务描述 - 相关知识 - 纯虚函数 - 特点 - 使用场景 - 作用 - 注意事项 - 相关概念对比 - 抽象类的使用 - 定义与概念 - 使用场景 - 编程要求 - 测试说明 - 通关代码 - 测试结果 **任务概述:** 1. **图形基类(Shape)**:包含纯虚函数 `void PrintArea()`。 2. **矩形类(Rectangle)**:继承 Shape 类,重写 `Print
48 4
|
6月前
|
C++
C++ PCL 计算多个RT矩阵变换后的变换矩阵
C++ PCL 计算多个RT矩阵变换后的变换矩阵
69 0
|
6月前
|
C++
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
67 0
|
6月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
146 0
C++多态崩溃问题之为什么在计算梯度下降时需要除以批次大小(batch size)
C++多态崩溃问题之为什么在计算梯度下降时需要除以批次大小(batch size)
|
7月前
|
C++一分钟之-编译时计算:constexpr与模板元编程
【7月更文挑战第2天】C++的`constexpr`和模板元编程(TMP)实现了编译时计算,增强代码效率。`constexpr`用于声明编译时常量表达式,适用于数组大小等。模板元编程则利用模板进行复杂计算。常见问题包括编译时间过长、可读性差。避免方法包括限制TMP使用,保持代码清晰。结合两者可以解决复杂问题,但需明确各自适用场景。正确使用能提升代码性能,但需平衡复杂性和编译成本。
164 3
|
8月前
|
C++一分钟之-编译时计算:constexpr与模板元编程
【6月更文挑战第28天】在C++中,`constexpr`和模板元编程用于编译时计算,提升性能和类型安全。`constexpr`指示编译器在编译时计算函数或对象,而模板元编程通过模板生成类型依赖代码。常见问题包括误解constexpr函数限制和模板递归深度。解决策略包括理解规则、编写清晰代码、测试验证和适度使用。通过实战示例展示了如何使用`constexpr`计算阶乘和模板元编程计算平方。
128 13
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等