刷题日记day16-字符串-N进制减法

---

文章目录

• 前言
• 一、问题复述
• 二、解法及其思想
• 三、代码实现及细节

---

前言

简单写个日记记录我刷了什么题以及心得总结。

---

一、问题复述

• 设计一个基于字符串的N进制减法。对输入的两个字符串按照给定的N进制进行减法操作，正确输出正负符号以及表示结果的字符串。
• 输入：在同一行以空格隔开的的三个参数。第一个N表示进制，第二个字符串参数表示被减数，第三个字符串表示减数
• 输出：在同一行的两个值。第一个值表示结果，-1表示出错，0表示结果为正数，1表示结果为负数。第二个数表示值。出错时省略第二个数。
• 限制：除开单独的0外，减数和被减数都不能以0开头。遇到0开头的数时视其出错。出错返回-1 。

二、解法及其思想

• 未规定进制的减法使用从低位到高位的按位减来处理比较合适。按位减有高位借位，此时就可以根据给定的进制基数来控制进制。
• 按位减法使用数的大小规定被减数和减数，正负符号单独处理。这样做比较方便。
• 其他的按照要求进行处理即可。

三、代码实现及细节

#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//字符串、数值相互转换
int charToValue(char c) {
	if (c < 'a')return c - '0';
	else return c - 'a';
}
char valueToChar(int v) {
	if (v < 10)return '0' + v;
	else return 'a' + (v - 10);
}


string nBaseSubtract(int base, string min, string sub) {
	if ((min.size() > 1 && min[0] == '0') || (sub.size() > 1 && sub[0] == '0'))return "-1";
	if (min == sub)return "0";
	string result;
	//先规定正负号
	//并补齐长度以便相减
	string a, b;
	if (min.size() < sub.size()) {
		result = "-";
		a = sub;
		b = min;
	}
	else if (min.size() == sub.size()) {
		for (int i = 0; i < min.size(); i++) {
			if (min[i] > sub[i]) {
				result = "";
				a = min;
				b = sub;
				break;
			}
			else if (min[i] < sub[i]) {
				result = "-";
				a = sub;
				b = min;
				break;
			}
		}
	}
	while (a.size() > b.size()) {
		b = "0" + b;
	}

	//从最低位开始相减
	int borrow = 0;//借位符号
	int diff;
	for (int i = a.size() - 1; i >= 0; --i) {
		int digit1 = charToValue(a[i]);
		int digit2 = charToValue(b[i]);
		digit1 -= borrow;
		if (digit1 < digit2) {
			digit1 += base;//借位
			borrow = 1;
		}
		else borrow = 0;
		diff = digit1 - digit2;
		result.push_back(valueToChar(diff));
	}
	//反转结果使其符合正序
	reverse(result.begin() + (result[0] == '-' ? 1 : 0), result.end());
	size_t start_pos = (result[0] == '-') ? 1 : 0;
	while (start_pos < result.size() - 1 && result[start_pos] == '0') {
		start_pos++;
	}
	if (start_pos > (result[0] == '-' ? 1 : 0)) {
		result = (result[0] == '-' ? "-" : "") + result.substr(start_pos);
	}
	if (result.empty() || (result[0] == '-' && result.size() == 1)) {
		return "0";
	}
	return result;
}

int main() {
	int n;
	string minuend, subtrahend;
	cin >> n >> minuend >> subtrahend;
	string s = nBaseSubtract(n, minuend, subtrahend);
	if (s == "-1")cout << "-1" << endl;
	else if (s[0] == '-') {
		cout << "1 " << s.substr(1);
	}
	else cout << "0 " << s << endl;
	return 0;
}