大约 20 分钟前,我刚刚完成了 C 入门类(class)的考试。考试的第一道题让我有些措手不及,涉及到求两个大数的差。
目标是按值获取两个结构(N1 和 N2),并将差异存储在按引用传递的结构 (N3) 中。我们被允许假设 N3 以全“0”启动。 MAX 大小可以是任何值,因此如果数字超过 100 位,该解决方案仍然有效。
这是基本代码(原始代码可能略有不同,这是凭内存)
#include <stdio.h>
#include <stdlib.h>
/* MAX can be any length, 10, 50, 100, etc */
#define MAX 10
struct bignum
{
char digit[MAX];
char decimaldigit[MAX/2];
};
typedef struct bignum bigNum;
void difference(bigNum, bigNum, bigNum *);
/*
Original values in N1 and N2
N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'};
N1.decimaldigit { '0', '0', '0', '4', '9' };
N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'};
N2.decimaldigit { '8', '0', '1', '2', '0' };
*/
/*
Result would be:
N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'}
N3.decimaldigit { '1', '9', '9', '2', '9' }
*/
问题不在于找到这个问题的解决方案,而是只提供了大约 20 行的完整答案。我的解题方法是将数字化为整数后一次减去一个数,如果结果为负数则进行适当的进位。这占用的空间比提供的空间多得多。
基于为这个问题提供的少量标记和空间,我相信有一个我没有看到的相当微不足道的解决方案。它是什么?我现在已经完成了类(class),但这个问题仍然困扰着我!
不需要完整的解决方案,只需要函数差异
的内部工作原理。
以防万一,不得使用按位运算符。
最佳答案
大多数计算机科学类(class)中的 BigNumber 问题旨在让您必须按照您描述的那样精确地“手动”进行算术运算:将每个字符转换为整数,减去并在适当的地方借位。
正如您所描述的那样,您的计划攻击应该只有几行。在伪代码中,是这样的:
for each character (right to left):
difference = N1.digit[i] - N2.digit[i];
if (difference < 0)
N1.digit[i - 1]--;
difference += 10;
N3.digit[i] = difference;
(加上一些额外的麻烦,将相同的逻辑也应用到十进制数字。)
听起来您的想法是正确的,也许只是对实现考虑过多?
关于c - C 中的大数减法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1316940/