题目描述
给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的差。
数据范围
1≤整数长度≤105
输入样例
32
11
输出样例
21
前言
减法的话是跟加法对称着写的,所以输入输出基本都一样,毕竟计算的时候加减乘除一般都在一起;借位可能会相
对难理解一点,
在此之前,大家要了解关于C++ vector的应用,这里简单列举一些常用的(其余的上网搜一下);
vector<int> a; //定义一个动态数组(动态数组是不需要定义数组大小)
a.back(); //返回a的最后一个元素
a.front();//返回a的第一个元素
a[i];//返回a的第i元素,当且仅当a存在
a.clear();//清空a中的元素
a.empty();//判断a是否为空,空则返回true,非空则返回false
a.pop_back();//删除a向量的最后一个元素
a.push_back(5);//在a的最后一个向量后插入一个元素,其值为5
a.size();//返回a中元素的个数
基本思路
首先,对于main里的,我们的思想是:1 输入数据. 2 倒序存入动态数组中. 3 计算. 4 倒序输出.
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');// 因为a是字符串类型的,当我们要存到int类型是,要进行一下转换;
for(int i = b.size() - 1; i >= 0; i -- )
B.push_back(b[i] - '0');
vector<int> C;//定义一个存结果的数组;
if(cmp(A,B))/* 判断,要考虑结果是负数的情况; 如果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;
}
判断的代码
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; // 这一步的话,相当于两个数相等了,直接true;
}
接下来就是模板了!!! 建议理解性记忆,不要死记硬背,主要的是思想,代码的实现好说;
减法;
/*说明一下,auto是可以自动匹配类型的,有时候为了代码长度的简便,会用auto来代替;
这个模板没用用到auto,先提一下吧!(auto不能作为返回值类型)*/
vector<int> sub(vector<int> &A, vector<int> &B)// 加&是为了避免再copy一次,减少时间;看个人习惯
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;//减t是为了之后循环的运算,即借位;
if (i < B.size()) t -= B[i];//// 若存在B[i],那么就计算;防止数组下标越界;
C.push_back((t + 10) % 10);
if (t < 0) t = 1;//需要借位
else t = 0;//不需要借位
}
while (C.size() > 1 && C.back() == 0) C.pop_back();//如果有前导0的话,直接干掉;
return C;
}
C.push_back((t + 10) % 10); 当t为负,说明我们需要借位,那么就+10 把他弄成正的,(再%10);
当t为正的 我们+10 再 % 10;对于t本身是没用变化的,简便了t为负的情况;可以理解为:我需要借位的话
,我就直接计算,然后再去判断;先斩后奏!
另外需要注意一下前导0;
本题代码
#include <iostream>
#include <cstring>
#include <algorithm>
#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 ++ )
{
t = A[i] - t;
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
while(C.size() > 1 && C.back() == 0) //如果有前导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;
}
这是我在一篇题解上看到的用普通的数组进行高精度减法的代码,不太明白的可以参考一下这篇题解
https://www.acwing.com/file_system/file/content/whole/index/content/526189/
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int A[N], B[N], C[N];
int Minus(int a[], int b[], int c[], int cnt) {
int t = 0;
for (int i=1; i<=cnt; i++) {
t = a[i] - b[i] - t;
c[i] = (t + 10) % 10;
if (t < 0) t = 1; else t = 0;
}
while (cnt > 1 && c[cnt] == 0) cnt --;
return cnt;
}
int main() {
string a, b;
cin >> a >> b;
if (a.size() < b.size() || a.size() == b.size() && a < b) {
cout<< '-';
swap(a, b);
}
int cnt1 = 0;
for (int i=a.size()-1; i>=0; i--)
A[++cnt1] = a[i] - '0';
int cnt2 = 0;
for (int i=b.size()-1; i>=0; i--)
B[++cnt2] = b[i] - '0';
int tot = Minus(A, B, C, max(cnt1, cnt2));
for (int i=tot; i>=1; i--)
cout << C[i];
}
基础比较好的同学,可以适当的向C加加转, 竞赛的时候C加加里边的一些函数用起来会比较的方便;(符号打不出来QAQ)