c++ - 将负数和正数相加到 10^100000
问题描述
我一直在尝试解决这个问题(从学校)大约一个星期。我们有两个数字,从 -(10^100000) 到 +that。
当然,最简单的解决方案是实现书面加法,这就是我所做的。我决定,我将使用两个函数将数字存储为字符串:
int ti(char a) { // changes char to int
int output = a - 48;
return output;
}
char tc(int a) { // changes int to char
char output = a + 48;
return output;
}
这样我可以存储负数,比如-2。考虑到这一点,我实现了一个 toMinus 函数:
void toMinus(std::string &a) { // 123 -> -1 -2 -3
for (auto &x : a) {
x = tc(-ti(x));
}
}
我还创建了一个 changeSize 函数,它将 0 添加到数字的开头,直到它们都是最大大小 + 1 和 removeZeros,它会删除前导零:
void changeSize(std::string &a, std::string &b) {
size_t exp_size = std::max(a.size(), b.size()) + 2;
while (a.size() != exp_size) {
a = '0' + a;
}
while (b.size() != exp_size) {
b = '0' + b;
}
}
void removeZeros(std::string &a) {
int i = 0;
for (; i < a.size(); i++) {
if (a[i] != '0') {
break;
}
}
a.erase(0, i);
if (a.size() == 0) {
a = "0";
}
}
毕竟,我创建了主要的 add() 函数:
std::string add(std::string &a, std::string &b) {
bool neg[2] = {false, false};
bool out_negative = false;
if (a[0] == '-') {
neg[0] = true;
a.erase(0, 1);
}
if (b[0] == '-') {
neg[1] = true;
b.erase(0, 1);
}
changeSize(a, b);
if (neg[0] && !(neg[1] && neg[0])) {
toMinus(a);
}
if(neg[1] && !(neg[1] && neg[0])) {
toMinus(b);
}
if (neg[1] && neg[0]) {
out_negative = true;
}
// Addition
for (int i = a.size() - 1; i > 0; i--) {
int _a = ti(a[i]);
int _b = ti(b[i]);
int out = _a + _b;
if (out >= 10) {
a[i - 1] += out / 10;
} else if (out < 0) {
if (abs(out) < 10) {
a[i - 1]--;
} else {
a[i - 1] += abs(out) / 10;
}
if (i != 1)
out += 10;
}
a[i] = tc(abs(out % 10));
}
if (ti(a[0]) == -1) { // Overflow
out_negative = true;
a[0] = '0';
a[1]--;
for (int i = 2; i < a.size(); i++) {
if (i == a.size() - 1) {
a[i] = tc(10 - ti(a[i]));
} else {
a[i] = tc(9 - ti(a[i]));
}
}
}
if (neg[0] && neg[1]) {
out_negative = true;
}
removeZeros(a);
if (out_negative) {
a = '-' + a;
}
return a;
}
这个程序在大多数情况下都有效,尽管我们的学校检查员发现它不 - 喜欢而不是
-4400547114413430129608370706728634555709161366260921095898099024156859909714382493551072616612065064
它回来了
-4400547114413430129608370706728634555709161366260921095698099024156859909714382493551072616612065064
我找不到问题所在。请帮助并提前感谢您。
解决方案
虽然我认为你的整体方法对于这个问题是完全合理的,但你的实现似乎有点太复杂了。试图自己解决这个问题,我想出了这个:
#include <iostream>
#include <limits>
#include <random>
#include <string>
bool greater(const std::string& a, const std::string& b)
{
if (a.length() == b.length()) return a > b;
return a.length() > b.length();
}
std::string add(std::string a, std::string b)
{
std::string out;
bool aNeg = a[0] == '-';
if (aNeg) a.erase(0, 1);
bool bNeg = b[0] == '-';
if (bNeg) b.erase(0, 1);
bool resNeg = aNeg && bNeg;
if (aNeg ^ bNeg && (aNeg && greater(a, b) || bNeg && greater(b, a)))
{
resNeg = true;
std::swap(a, b);
}
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0)
{
const int digitA = (i >= 0) ? a[i] - '0' : 0;
const int digitB = (j >= 0) ? b[j] - '0' : 0;
const int sum = (aNeg == bNeg ? digitA + digitB : (bNeg ? digitA - digitB : digitB - digitA)) + carry;
carry = 0;
if (sum >= 10) carry = 1;
else if (sum < 0) carry = -1;
out = std::to_string((sum + 20) % 10) + out;
i--;
j--;
}
if (carry) out = '1' + out;
while (out[0] == '0') out.erase(0, 1);
if (resNeg) out = '-' + out;
return out;
}
void test()
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(-std::numeric_limits<int32_t>::max(), std::numeric_limits<int32_t>::max());
for (int i = 0; i < 1000000; ++i)
{
const int64_t a = dis(gen);
const int64_t b = dis(gen);
const auto expected = std::to_string(a + b);
const auto actual = add(std::to_string(a), std::to_string(b));
if (actual != expected) {
std::cout << "mismatch expected: " << expected << std::endl;
std::cout << "mismatch actual : " << actual << std::endl;
std::cout << " a: " << a << std::endl;
std::cout << " b: " << b << std::endl;
}
}
}
int main()
{
test();
}
它可能会进一步优化,但要点是:
- 如果两个数的符号相同,我们可以做简单的书面加法。如果两者都是负数,我们只需
-
在最后添加。 - 如果符号不同,我们会做书面减法。如果被减数大于减数,就没有问题,我们知道结果是肯定的。但是,如果减数更大,我们必须重新表述问题。例如,
123 - 234
我们将制定为-(234 - 123)
。我们可以使用常规的书面减法来解决内部部分,然后我们在前面加上-
.
我用随机数对此进行测试,我们可以使用常规整数算术计算出正确的结果。由于它不会失败,我非常有信心它也适用于更大的输入。像这样的方法还可以帮助您发现实施失败的情况。
除此之外,我认为您应该将已知的失败案例与调试器一起使用,或者简单地打印中间步骤的语句以查看失败的位置。您发布的失败示例中唯一的小差异可能指向处理结转的一些问题。
推荐阅读
- javascript - 如何以编程方式关闭选择文件对话框
- java - 将 JDBC 连接到 IP 地址
- javascript - 在 2 个已排序的 JS 对象中查找更改的位置
- java - Oauth2资源服务器中AuthenticationManagerBuilder的目的是什么
- python - 使用 scipy truncnorm 拟合数据
- c# - 如何总结数据库中给定日期的多个时间记录。错误:子查询返回超过 1 个值
- reactjs - 打字稿:在类中初始化事件侦听器
- css - 如何正确使用媒体查询使一列消失而另一列调整为屏幕宽度?
- javascript - 在预期的角度属性或签名中制作参数时出错
- java - Maven Jaxb 插件 implClass 绑定不起作用