首页 > 编程语言 >算法基础1.3.2高精度减法

算法基础1.3.2高精度减法

时间:2023-03-04 16:35:06浏览次数:34  
标签:10 高精度 1.3 vector 减法 我们 size

前言

先看高精度加法的文章,如果没有看,我把高精度加法文章中的总结前言放到这里

该文章探讨的高精度代指C++中极大整数的计算,不是浮点数(y总说那个少见,不讲)。

这个问题只在C++中存在,Java有大整数类来解决,python本身特性就已经解决了。

高精度整数分为四种类型:A+BA-BA*a(一个大数乘一个小数),A / a(一个小数除一个大数)。这里面的大数(大写字母)极端一点的话,它的位数能来到10的6次方。小数(小写字母)他的数值一般是10000。

对于高精度整数,我们的存储方式一般是数组,每一个数组位置保存一个数。

下文我们都是使用的C++中的vector而非数组array,使用数组也可以,但是vector提供的方法会更加便利。比如我们得到内容长度,vector可以直接使用他的函数length(),而数组则需要我们利用sizeof(a)/sizeof(a[0])去计算。

正文开始之前我们再谈一下四个算法的共性:

  1. 数据存储方面,我们是把个位存在0位置,十位存在1位置....这虽然相当于让我们的数倒过来了,但是目的是相当有用的。如果在进行计算时我们这个数要进位,那么比起把所有数往后面挪一位再把进位的数放到第0位,肯定是直接把进位的数加到数组最后一位更加轻松,同时运算也更快
  2. 思路方面,其实就是人工模拟计算过程,跟我们在演草纸上计算的思路一样。

在学会高精度加法后,我们就已经将四个算法的整体架构学会了,我们的存储方式都是一样的。我们需要改动的只有函数的内容,而指导思想都是一样的,就是使用代码人工模拟算法计算过程。

正文

这里有几个新的思想

  • 我们始终保持被减数大于减数,这样可以让我们的运算思路唯一。面对结果为负的情况(此时被减数小于减数),我们就让两者减法顺序互换,保证函数运算结果为正值,然后在最后的输出中输出一个-即可
  • 就像上面加法一样,我们对于减法思路也可以进行拆解:当前位的值 = 被减数当前位的值 - 减数当前位的值 - 上一位借的1(如果有的话)

注意:下面的代码只考虑了两个数都是正数的情况,对于其他情况要使用其他模板。因为对于任意两个数相减,我们都可以换成两个数的绝对值相减(同号,并且同负号情况下需要整体再加一个符号或者将他们的位置反转),或者两个数的绝对值相加(异号,同时其中一种情况要整体加一个负号)

#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();
	//如果位数一样,再从最大位数开始一个数一个数的比较
    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;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        // 下面两行代码将A[i]-B[i]-t进行了拆分(因为-B[i]这个要分情况讨论)
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        // 这个其实是将两种情况整合了,具体哪两种情况,看下面的解释
        C.push_back((t + 10) % 10);
        // 计算下一位是否被此位借1了
        if (t < 0) t = 1;
        else t = 0;
    }
	//把前置0都去掉,比如003这种。同时保证答案为0时不去掉
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> 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');

    vector<int> C;
	
    // 调整两个数关于除数与被除数的关系
    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;

    return 0;
}

现在我们解释一下函数里对t的使用,这个t既作为当前位结果的一个记录,又作为借位的标记来传递给下一次循环(进入下一次循环前t=1说明下一位被当前借了1)

  1. 我们一开始将t初始化为0(在for循环语句中),这是因为个位数上的借位情况一定是没有被借位(t值为0)
  2. 后面我们使用的t = A[i] - t;if (i < B.size()) t -= B[i];便是遵循我们的减法思路。其实这里可以开个新的变量来存储当前值,但是使用t就够了。
  3. 算出当前值t后,如果
    • 为正,说明不需要借位,这个位置上的数就是t本身
    • 为负,说明经过减法后欠了一些数,需要找下一位借1,借完1后当前位的数就是t+10(这属于小学就知道的思想,只不过放代码里了)
    • 而我们的(t + 10) % 10就巧妙地将两个情况结合在了一起
  4. 注意上面放入容器中的操作我们并没有改变t的值,他现在还是有正负的。我们此时根据他的符号就可以判断它有没有找下一位借1
    • 如果借了(负值),那么t变为1。在下次循环中,他会给下一位的数减一
    • 如果没借(正值),那么t变为0,在下一次循环中对结果没有影响

标签:10,高精度,1.3,vector,减法,我们,size
From: https://www.cnblogs.com/zaughtercode/p/17178507.html

相关文章

  • 算法基础1.3.3高精度乘法
    前言先看高精度加法的文章,如果没有看,我把高精度加法文章中的总结前言放到这里该文章探讨的高精度代指C++中极大整数的计算,不是浮点数(y总说那个少见,不讲)。这个问题只在C......
  • 高精度计时QueryPerformanceFrequency/QueryPerformanceCounter
    提供非中断的时间获取,精确到微秒级头文件:#include<windows.h>函数:QueryPerformanceCounter(&T)T是一个LARGE_INTEGER结构体,内部是longlong数据类型,获取到当前C......
  • 谱减法(二)使用自适应增益的谱减法
    原书:语音增强--理论与实践前言谱减法中导致音乐噪声(信号帧频谱的随机位置上出现小的,独立的峰值,称为音乐噪声)的两个因素在于:(1)谱估计的大范围变化、(2)增益函数的不同。为......
  • 11.3 shtctl的指定省略(harib08c)
    ps:能力有限,若有错误及纰漏欢迎指正、交流11.3shtctl的指定省略(harib08c)对bootpack.h做了如下改动structSHEET{unsignedchar*buf;intbxsize,bysize,vx0,vy0......
  • 消费级显卡的春天,GTX 3090 YOLOv5s单卡完整训练COCO数据集缩短11.35个小时
    前言 本文介绍了在单卡上凭借对YOLOv5的性能分析以及几个简单的优化将GTX3090FP32YOLOv5s的训练速度提升了近20%。对于需要迭代300个Epoch的COCO数据集来说相比ultral......
  • 高精度-----大整数类模板
    代码如下#definemaxn100structBigint{ intlen,a[maxn];//用len记录位数,a记录每个数位 Bigint(intx=0){//通过初始化使得这个大整数能够表示整型x,默认为0 memset......
  • 1.3 抽象数据类型的表示与实现
    1.3抽象数据类型的表示与实现概念小结抽象数据类型的实现C语言实现抽象数据类型抽象数据类型可以通过固有的数据类型(如整形、实型、字符型等)来表示和实现即利用......
  • KingbaseES libstdc++.so.6 version 'CXXABI_1.3.8'问题处理
    概述initdb报错如下:“ERROR:libstdc++.so.6:version:'CXXABI_1.3.8'notfound(requiredby...)”此文是以CentOSLinux7(AltArch)操作系统为例,编译安装高版本GC......
  • Kali 2021.3 安装ARL (资产侦察灯塔系统)
    0x00准备工作下载kali镜像:https://www.kali.org/get-kali/ARL:https://github.com/TophantTechnology/ARL0x01Docker安装ARL目前不支持Windows,Linux和Mac建议Docker安......
  • 高精度
    高精度加法#include<bits/stdc++.h>usingnamespacestd;vector<int>add(vector<int>&A,vector<int>&B){vector<int>C;if(A.size()<B.size())......