【基础算法】关于高精度计算的问题【很高位数数据的加减乘除(相关代码用C++实现)】

简介: 【基础算法】关于高精度计算的问题【很高位数数据的加减乘除(相关代码用C++实现)】

前言


当我们在利用计算机进行一些计算时,可能会遇到这类问题 : 有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。

这时我们就可以通过程序设计来解决这类问题,例如:创建一个数组,通过数组来存放高精度数的每一位上的数。


1.高精度加法


高精度加法是两个位数很大的两个数相加,例如1234567898756432123456789 + 66666666666666666666666,这时候我们用平常的整型或者长整型去存放数据都是会溢出导致数据丢失的,所以此时我们可以用一个数组来存放每个数相对应位上的数(使用vector<int>, 假设这两个高精度数都大于0)。


不过在C++中,直接将数输入到vector中是不可取的,并且加法是从两个数的低位开始相加一直加到高位,如果我们正常输入从高位开始存放的话,对于后面程序的设计是不方便的,所以这里我们用string来表示相应高精度数,然后将这个string从低位开始转化成整数依次存放在vector<int>当中,这样两个vector<int>就是我们想要的高精度数了。


同时我们需要另一个vector<int>来存放相加后的数,由于相加数的存放是倒着的,所以最终的结果也是倒着存放在vector<int>中的,此时打印就需要从后面往前面打印输出。


加法不难,但要注意的是,如何在程序中表示进位,我们都知道,每一位数相加超过10就要进位1,表示这一位的前一位要+1。3和5相加为8不用进位,而7和8相加要进位,最后在这一位留下来的是(7 + 8)- 10 = 5,在程序中可以表示为(7 + 8)% 10。而这个%10就显得格外重要了,如果你相加后的数小于10,它%10后,还是它本身,如果大于10,它就相当于去掉一个10,剩下的数就放进表示最终答案的vector<int>。


最后要注意的是,两个位上的数相加后的结果要/=10,这是表示要除去这一位该留下的结果以及得到需要进的位,例如:7 + 8 = 15 ,在该位应该留下的最终结果为 15 % 10 = 5,最后 15 /= 10 得到1,表示要进位1,该位的结果5除去。


下面是相关操作的代码实现:

#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int>& A, vector<int>& B)
{
  vector<int> C;
  int tmp = 0;
  for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
  {
    if (i < A.size()) tmp += A[i];
    if (i < B.size()) tmp += B[i];
    C.push_back(tmp % 10);
    tmp /= 10;
  }
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}
int main()
{
  string a, b;
  cin >> a >> b;
  vector<int> A, B;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  auto C = add(A, B);
  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  cout << endl;
  return 0;
}



代码测试:


5c03452b71d34e36ac4f1008d6c9c5f3.pngb137a7adc8164db69a9b9d9db43a2407.png


代码细节解释:

  • 这里是将高精度数分别从低位到高位存放到两个vector<int>中;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  • 这个for循环便是相加的代码,两个if表示如果这个数的位数加完了,就停止加入tmp,判断条件表示将tmp加完为止(也就是如果两个数位数相同,最高位相加完后又进了一位,此时 tmp 为 1 并且不在加入数据,这个1 也是有效位,因此需要加入C中)
  for (int i = 0; i < A.size() || i < B.size() || tmp; i++)
  {
    if (i < A.size()) tmp += A[i];
    if (i < B.size()) tmp += B[i];
    C.push_back(tmp % 10);
    tmp /= 10;
  }
  • 这个while表示去掉前导0,虽然加法不会出现前导0的情况,但不排除输入的数据都为0的情况。
while (C.size() > 1 && C.back() == 0) C.pop_back();


2.高精度减法


高精度减法是两个很高位数的数相减,值得注意的是,减法需要借位,并且相减会出现结果为正还是负的情况,因此,高精度减法的程序比高精度加法的程序稍复杂。


对于结果是正还是负的情况,我们可以写一个cmp函数对存放两个高精度数的string进行比较,然后规定sub函数第一个参数为大的那个数,我们只要将大的那个传入第一个参数即可。如果是第二个输入的高精度数较大,在打印结果的时候先打印一个‘ - ’即可。


在进行相减的时候,我们可以先定义一个标记借位的变量tmp(初始化为0),如果一位上相减为负数,说明需要向前借一位,所以在减的循环中第一条语句可以为:tmp = big[i] - tmp;,如果结果小于零,将tmp置为1,等进入下一次循环,第一条语句就自动减一,起到借位的效果。


那么结果小于0,我们该如何确定这一位的最终答案呢?我们只需要在push_back时,里面的参数设为(tmp + 10)% 10,这样就可以处理tmp所有的情况了(详细点看代码注释)。


由于我们是通过将高精度数的每一位存入数组来计算的,并且减法会出现最高位依次连续是0的情况,因此作为答案的数组,高位可能存放有0,在打印的时候这些0都会被打印出来,所以这里要有删去高位0的操作。


下面是相关操作的代码实现:

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int>& A, vector<int>& B)
{
  if (A.size() != B.size()) return A.size() > B.size();
  // 这一步说明A,B两个高精度数长度相等,此时从最高位依次比较
  for (int i = A.size() - 1; i >= 0; i--)
    if (A[i] != B[i])
      return A[i] > B[i];
  return true;
}
vector<int> sub(vector<int>& A, vector<int>& B)
{
  vector<int> C;
  int tmp = 0; // 用来标记借位
  // 这里A要大,所以 i < A.size()
  for (int i = 0; i < A.size(); i++)
  {
    tmp = A[i] - tmp; // 表示上一步有没有借位
    if (i < B.size()) tmp -= B[i];
    // (tmp + 10) % 10 这是因为:
    // 当tmp<0时,说明这一位A的小于B的,因此要借位
    //    所以tmp+10后就相当于借位后的数,%10后便是留在这一位的最终结果
    // 当tmp>0时,说明这一位A的大于B的,尽管加了10
    //    但%10后加10与不加10是一样的(可脑补一下)
    C.push_back((tmp + 10) % 10);
    // 如果tmp<0,表示这一位A的小于B的,因此将tmp置为1,下一次循环的第一步减去一
    if (tmp < 0) tmp = 1;
    else tmp = 0;
  }
  // 由于高位会出现0的情况(22226 - 22223 = 3),所以这里要去前导0
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}
int main()
{
  string a, b;
  cin >> a >> b;
  vector<int> A, B;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
  if (cmp(A, B))
  {
    auto C = sub(A, B);
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  }
  else
  {
    auto C = sub(B, A);
    cout << '-';
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  }
  return 0;
}



代码测试:


49f9ef55749846d9a191e01ee6702785.png


606286685844435fa30fdfeceedeac04.png

3.高精度乘法


在学完高精度加法和减法后,对于高精度乘法理解起来是很快的,这里我们规定,输入的第一个数为高精度数,第二个数为int范围内的数,并且两个数都是正整数。


有了上面的规定,接下来的操作就简单了,我们只需要关注如何乘,如何push,以及去前导0即可。


相乘前的准备与高精度加减类似,只不过输入的其中一个参数变为了int 。


整个相乘的过程:定义一个tmp ,将高精度数的每一位与int数相乘加入tmp(每一次循环将每一位相乘后的结果加入tmp),然后每一次循环中,将tmp%10(每次取出个位上的数)push_back,再tmp/=10丢掉个位上的数,直到高精度的每一位数都乘过或者tmp为0循环结束,这样就完成了高精度的乘法。


如果输入的两个数有0,那么结果终究会是0,所以高精度乘法也要有去除前导零的操作。


下面是相关操作的代码实现:

#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A, int b)
{
  vector<int> C;
  int tmp = 0;
  for (int i = 0; i < A.size() || tmp; i++)
  {
    // 如果A没有遍历完就一直将每一位与b相乘加入tmp
    if (i < A.size()) tmp += A[i] * b;
    // (tmp % 10)是push tmp的个位
    C.push_back(tmp % 10);
    // 丢弃个位
    tmp /= 10;
  }
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}
int main()
{
  string a;
  int b, flag = 1;
  cin >> a >> b;
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  auto C = mul(A, b);
  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  return 0;
}



代码测试:

0789dd5f07d64ac08af4dbf4900d5d23.png

e04bf36df71b413f9ab85e4f8af561e6.png


选取测试案例图解:

30eab85100774a868d2290af88e3c523.png


4.高精度除法


高精度除法与高精度乘法相比,多了一个变量r用来储存余数,其余的输入与乘法相同,但最后输出要把r打印。同样的,这里我们规定,两个数都是正整数,并且int范围内的那个数不能为0(一个高精度数除以一个int范围内的整数)。


对于整个相除的过程,肯定也是需要一个循环的。我们都知道,每一位相处的余数,都要相当于乘以10与下一位相加,由于r初始为0,因此循环的第一句可以写为r = r * 10 + A[i] ,A[i]为当前位的数,r*10表示上一位数相除得到的余数,如果上一位数余数为零,则这个表达式结果为0。


执行完上一条语句后便得到了被除数,此时就可以push:r / 除数,表示当前位的结果,最后再r %= 除数 除去除完的除数,这样整个过程就设计完成了。


由于main函数打印正确答案是从尾开始将每一位打印到头的,并且正确答案是由高位到低位从数组的头依次存放的,因此下一步需要逆置一下结果数组。


最后,除法会有高位为0的情况,因此还要有一步去除前导0的操作。


下面是相关操作的代码实现:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 要改变main函数里的余数r,因此要引用
vector<int> div(vector<int>& A, int b, int& r)
{
  vector<int> C;
  // 根据除法的过程,从高位开始除
  for (int i = A.size() - 1; i >= 0; i--)
  {
    // r开始为0,则第一次循环就为A的最高位与b相除
    // 如果 r>b 则会有余数 ,所以下一次循环将这个余数 乘以10+A[i] 便是第二次循环要除的数
    // 如果 r<b 则余数就是r本身,第三条语句 r%=b 就相当于没执行过
    r = r * 10 + A[i];
    C.push_back(r / b); // push 这一次除b的结果,如果r<b,则push:0
    r %= b;
  }
  // 由于得到的结果是从高位向低位开始存的,所以这里逆置一下,便于去除前导0
  reverse(C.begin(), C.end());
  // 除法会出现0的情况,因此这里要处理前导0
  while (C.size() > 1 && C.back() == 0) C.pop_back();
  return C;
}
int main()
{
  string a;
  // b为int范围内的数
  // 创建一个变量r来储存余数
  int b, r = 0;
  cin >> a >> b;
  // A用来储存高精度数
  vector<int> A;
  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
  auto C = div(A, b, r);
  // 打印还是与前面一样,因为div中结果逆置了
  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
  // 这里打印余数
  cout << endl << r << endl;
  return 0;
}



代码测试:

4f144218cdd448cfa43b06d12d1197a3.png

d9f5202692df48169fa332cd220aed71.png


选取测试案例图解:

输入

128

8

输出

16

0


dc825f28adb44cac9f64f5aa1b81bde2.png


写在最后


上述可以说都是高精度计算的基础模板,实际上在很多题目中都可以用到这一模板,比如某些链表的题。所以我们要增强对这一类模板的熟练度,以便在后面的刷题中遇到能用此模板解决的问题能够想起来有这一模板可以用。


感谢阅读本小白的博客,错误的地方请严厉指出噢!

目录
打赏
0
0
0
0
3
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
70 1
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
83 17
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
Paper2Code是由韩国科学技术院与DeepAuto.ai联合开发的多智能体框架,通过规划、分析和代码生成三阶段流程,将机器学习论文自动转化为可执行代码仓库,显著提升科研复现效率。
354 19
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
AI是如何收集体育数据的?从摄像头到算法,揭秘赛场背后的“数字间谍网“!
⚽ 你是否好奇:AI如何知道哈兰德每秒跑多快?教练的平板为何比裁判还清楚谁偷懒?本文揭秘AI收集体育数据的“黑科技”:视觉追踪、传感器网络、数据清洗与高阶分析。从高速摄像机捕捉梅西肌肉抖动,到GPS背心记录姆巴佩冲刺速度;从表情识别判断装伤,到量子计算模拟战术可能,AI正让体育更透明、精准。未来已来,2030年世界杯或将实现AI替代球探、裁判甚至教练!你认为AI数据收集算侵犯隐私吗?最想统计哪些奇葩指标?留言互动吧!
|
3月前
|
UE5 C++:自定义Http节点获取Header数据
综上,通过为UE5创建一个自定义HTTP请求类并覆盖GetResult方法,就能成功地从HTTP响应的Header数据中提取信息。在项目中使用自定义类,不仅可以方便地访问响应头数据,也可随时使用这些信息。希望这种方法可以为你的开发过程带来便利和效益。
134 35
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
35 0
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
181 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
|
1月前
|
C++
爱心代码 C++
这段C++代码使用EasyX图形库生成动态爱心图案。程序通过数学公式绘制爱心形状,并以帧动画形式呈现渐变效果。运行时需安装EasyX库,教程链接:http://【EasyX图形库的安装和使用】https://www.bilibili.com/video/BV1Xv4y1p7z1。代码中定义了屏幕尺寸、颜色数组等参数,利用随机数与数学函数生成动态点位,模拟爱心扩散与收缩动画,最终实现流畅的视觉效果。
63 0
AI助理

你好,我是AI助理

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