#gj002. 高精度减法

高精度减法

高精度减法

题目描述

​ 给定两个非负整数 A 和 B,它们的位数可能超过普通整数类型(如 int 或 long long)的表示范围。请使用高精度减法(Big Integer Subtraction) 计算 A - B 的值,并输出结果。若 A < B,则输出负数和绝对值。

算法概念

​ 高精度减法(大整数减法)是处理超过基本数据类型表示范围的整数减法运算的常用方法。其核心思想是将大整数按位存储在数组中,从最低位(个位)开始逐位相减,若不够减则向高位借位,最终得到精确的计算结果。该方法模拟了手工竖式减法的过程。

算法原理与步骤

  1. 字符串读入:将两个大整数以字符串形式读入,方便处理任意长度的数字。
  2. 比较大小并确定符号:若被减数小于减数(长度更短,或长度相同但字典序更小),则交换两者,并标记结果为负数。
  3. 逆序存储:将字符串中的数字字符转换为整数,并逆序存入整型数组(数组下标 0 对应个位,下标 1 对应十位,以此类推)。
  4. 逐位相减:从低位到高位遍历,用被减数的当前位减去减数的对应位。若不够减(a1[i] < b1[i]),则向高位借 1(a1[i+1]--),当前位加 10 后再减。结果存入 c1[i] = a1[i] - b1[i]。
  5. 去除前导零:从最高位开始,跳过所有高位的 0,确定实际输出长度。
  6. 输出结果:若结果为负数,先输出负号,然后从最高非零位到最低位依次输出。若结果为 0,则输出单个 0。

输入格式

​ 第一行一个非负整数 A(可能很大)。

​ 第二行一个非负整数 B(可能很大)。

输出格式

​ 一行,输出 A - B 的结果(不含前导零,若结果为负则先输出负号,若结果为 0 则输出 0)。

输入输出样例

输入输出样例 #1

123456789
987654321
-864197532

输入输出样例 #2

987654321
123456789
864197532

输入输出样例 #3

5
5
0

数据规模与约定

  • A 和 B 均为非负整数,长度不超过 200 位。
  • 结果长度不超过 201 位(含负号)。
  • 时间限制:1 秒
  • 内存限制:256 MB

提示

​ 代码提示:

char a[205], b[205];
cin >> a >> b;

int la = strlen(a), lb = strlen(b), lc;
int a1[205] = {}, b1[205] = {}, c1[205] = {};

// 判断是否需要交换(被减数小于减数)
if (la < lb || ( ? && strcmp(a, b) < 0)) {
    swap(la, lb);
    swap(a, b);
    cout << "-";   // 结果为负数
}

// 将 a 逆序存入 a1
for (int i = 0; i < la; i++) {
    
}
// 将 b 逆序存入 b1
for (int i = 0; i < lb; i++) {
    
}

// 逐位相减
for (int i = 0; i < la; i++) {
    
}

// 去除前导零
lc = la - 1;
while (c1[lc] == 0 && ?) {
    // TODO: lc--;
}

// 输出结果
for (int j = lc; j >= 0; j--) {
    cout << c1[j];
}	

​ 运用提示:

  • 高精度减法的核心是“逐位相减,借位处理”。借位时,高位减 1,当前位加 10。
  • 比较两个大数大小时,先比长度,长度相同则用 strcmp 比较字典序。
  • 借位操作需注意,a1[i] 和 a1[i+1] 会随借位动态变化,但因为是逐位从左到右(低位到高位)处理,所以更新后的值会正确参与后续计算。
  • 去除前导零时,用 lc 记录最高非零位下标。若结果为 0,循环条件 lc > 0 会保证最后保留最低位 0。
  • 注意 swap(la, lb) 和 swap(a, b) 的顺序,若先交换 a 和 b,则 la 和 lb 需同时更新以匹配新的字符串长度。