c - 从左到右添加 2 个大数
问题描述
是否可以在不反转数组的情况下添加 2 个大数?我必须使用这个函数声明:
int add(const char* n1, const char* n2, char** sum);
我不能反转数组,因为它是cosnt char*
:(
解决方案
我认为这是一个挑战——下面的代码从左到右添加了两个非负数字符串。它只是从更长的时间直到数字排成一行,然后逐个字符地添加。如果有进位,它会从右到左传播它来修复已经求和的数字:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int add(const char *n1, const char *n2, char **sum) {
const char *longer = n1, *shorter = n2; // ['1', '2', '3'] + ['8', '9']
size_t bigger = strlen(longer), smaller = strlen(shorter); // 3, 2
if (smaller > bigger) {
shorter = n1;
longer = n2;
size_t temporary = smaller;
smaller = bigger;
bigger = temporary;
}
*sum = malloc(bigger + 2); // 3 + carry + null byte
(*sum)[0] = '0';
(*sum)[bigger + 1] = '\0'; // ['0', x, x, x, '\0']
for (int power_of_ten = bigger; power_of_ten > 0; power_of_ten--) { // 3 ... 1 (for length comparison)
size_t idx = bigger - power_of_ten; // 0 ... 2 (for indexing left to right)
if (power_of_ten > smaller) {
(*sum)[idx + 1] = longer[idx]; // just copy from longer to sum
} else {
char c = shorter[idx - (bigger - smaller)] + longer[idx] - '0'; // add
(*sum)[idx + 1] = c;
for (int j = idx + 1; j > 0 && (*sum)[j] > '9'; j--) { // backward carry
(*sum)[j] -= 10;
(*sum)[j - 1] += 1;
}
}
}
if ((*sum)[0] == '0') { // ['0', '2', '1', '2'] -> ['2', '1', '2']
for (int j = 0; j < bigger + 1; j++) {
(*sum)[j] = (*sum)[j + 1];
}
}
return 42; // problem didn't specify what `int add(...)` returns
}
int main() {
char a[] = "509843702", b[] = "430958709432";
char *s;
(void) add(a, b, &s);
printf("%s\n", s);
(void) free(s);
return 1;
}
输出
> ./a.out
431468553134
>
查看
> dc
509843702 430958709432 + p
431468553134
>
此添加涉及五个进位,其中三个是独立的(不是级联)。
推荐阅读
- variables - TFS/VSTS,在一个变量中引用一个变量
- java - 这是制作继承对象的唯一方法吗?
- mysql - 添加外键约束失败
- api - Lua API 卸载 luaL_loadfile
- python-3.x - 如何从另一个 Python 3 脚本中获取变量?
- python - 从 matplotlib 频谱图中删除微秒
- php - PHP 创建一个具有预定义列和宽度的字符串
- django - Docker:使用 localhost 而不是 db 连接到 PostgresDatabase
- mysql - 我在子查询 MySQL 的 Where 子句中使用 NOT IN 和 IF 是正确的方式吗?
- python - 如何将列表中的集合转换为python中的列表?