C++信奥之径，锻炼思维，扎实算法——模拟与高精度算法(4)

【模版题】高精度减法

题目描述

算法解析

1、与上期的高精度加法类似，本题的数字由于最多到达10086位，C++中能存储数据位数最多的_int128类型（在后续的编程技巧中会介绍这一个特殊的大存储类型）也存储不下这个数字，所以需要使用高精度减法来计算结果。

2、同样需要先解决存储两个减数的问题，用字符串string或字符数组char[]来存储。

3、高精度减法的算法原理也是小学数学的减法竖式计算，过程为：（1）数位对齐；（2）从个位开始减，不够就借位；（3）存储结果，计算最终答案的位数，以便去掉前导0。

接下来用程序设计语言描述整个过程。

01

数位对齐

这部分代码与高精度加法一致，可以参考前一篇文章（点击跳转查看）。

同时，在初始化的时候，需要判断a和b的大小，我们只做a>b的减法。如果a-b<0，那么根据减法的规则，a-b = -(b-a)，需要交换a和b，并输出负号。

02

从个位开始减，不够就借位

每一位a[i]-b[i]后，需要判断减下来的结果，如果>=0就正常相减，如果<0，说明a[i]需要向高位借1才能与b[i]相减，此时需要c[i+1]--来实现向高位借一，同时要注意高位的减法答案因为借位要-1，而-1也会反馈在高位的减法中。

因此，可以每次将借位的情况传递到c[i+1]上去，如果c[i+1]==0，就表示没有借位，如果c[i+1]==-1，表明前一位减法有借位。因此当前位的减法应该要类似于下面的代码：

c[i] = a[i] - b[i] + c[i]; //+c[i]的目的是加上之前是否有的借位
if(c[i] < 0){
  c[i+1]--; //先借位
  c[i]+=10; //再算出真正结果
}

03

存储结果，计算最终答案的位数，以便去掉前导0

在初始化数据时，我们会大致判断答案数组c的大小肯定不大于max(lena,lenb)，即a和b字符串中较大的那个。

但是，如果a和b的长度一致，那么相减得到的结果c可能会位数很少，例如10001-10000=1，但是c数组中储存的答案为00001，这时候就需要去掉前导0来保证答案为数学数字。

使用while循环，当c数组的首位是0时，lenc--，从而获取到正确的答案数组c的长度。具体代码为：

while(c[lenc-1]==0 && lenc>0) //lenc>0是以防最终答案是0的情况
    lenc--;

【参考代码】

#include<bits/stdc++.h>
using namespace std;
int a[10001],b[10001],c[10002],lena,lenb,lenc;
int main(){
  string l1,l2;
  cin>>l1>>l2;
  lena=l1.length();lenb=l2.length();
  //判断a和b的大小 
  if(lena<lenb || (lena==lenb && l1<l2)){
    swap(l1,l2);
    cout<<"-";
  }
  //处理数字
  lena=l1.length();
  lenb=l2.length();
  for(int i=0;i<lena;i++)
    a[lena-i]=l1[i]-'0';
  for(int i=0;i<lenb;i++)
    b[lenb-i]=l2[i]-'0';
  lenc=max(lena,lenb);
  //模拟竖式相减
  for(int i=1;i<=lenc;i++){
    c[i]=a[i]+c[i]-b[i];
    if(c[i]<0){
      c[i+1]--;
      c[i]+=10;
    }
  }
  //处理答案的前导0 
  while(c[lenc-1]==0 && lenc>0)
    lenc--;
  //如果0都被处理掉了，那么答案就是0
  if(lenc==0){
    cout<<0;
  }
  else{
    for(int i=lenc;i>0;i--)
      cout<<c[i];
  }
  return 0; 
}

代码中的C++知识解读

swap()函数

在C++的std标准库中，我们常用swap()函数来进行两个变量或元素的交换，其中函数模版为：

swap()函数

在C++的std标准库中，我们常用swap()函数来进行两个变量或元素的交换，其中函数模版为：

void swap(T &a,T &b){
  T c(a);
  a = b;
  b = c;
}

代码中的T为类型，根据实际需要可以使用相应的类型。swap()函数支持相同数据类型的变量值相互交换，例如：

int a,b;
float x,y;
string s1,s2;
//赋值后
swap(a,b);
swap(x,y);
swap(s1,s2);

特别地，在string字符串和vector可变数组的函数中，也有自带成员函数swap()：

string s1,s2;
s1.swap(s2);
vector<int> a1,a2;
a1.swap(a2);

从而实现两个字符串、两个数组内容的交换，并且vector数组在经过容器交换后，还能实现内存空间的收缩，从而节约内存。

运行结果