6

大约 20 分钟前，我刚刚完成了 C 入门课程的考试。考试的第一个问题让我有点措手不及，涉及找出两个大数的差异。

目标是按值获取两个结构（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 行来提供完整的答案。我的解决方法包括在转换为整数后一次减去一个数字，然后在结果为负数时进行适当的进位。这比提供的空间大得多。

基于为这个问题提供的少量标记和空间，我相信有一个我没有看到的相当微不足道的解决方案。它是什么？我现在已经完成了课程，但这个问题仍然困扰着我！

不需要完整的解决方案，只需要函数的内部工作difference。

不使用位运算符，以防万一。

4

3 回答 3

10

大多数计算机科学课程中的 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;

（加上将相同的逻辑应用于十进制数字的一些额外麻烦。）

听起来您的想法是正确的，也许只是过度考虑了实施？

于 2009-08-22T20:27:28.283 回答
6

如果N1 >= N2. 这也假设数组的布局类似于dn...d2d1d0.e0e1...em.

char digchr(int); // Converts a single-digit integer into a character.

void difference(bigNum N1, bigNum N2, bigNum *N3) {
    int carry = 0;

    for (int i = MAX / 2 - 1; i >= 0; i--) {
        int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry;
        if (diff < 0) { 
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }

        N3->decimalDigits[i] = digchr(diff);
    }

    for (int i = 0; i < MAX; i++) {
        int diff = N1.digits[i] - N2.digits[i] - carry;
        if (diff < 0) {
           diff += 10;
           carry = 1;
        } else {
            carry = 0;
        }

        N3->digits[i] = digchr(diff);
    }
}
于 2009-08-22T20:28:40.247 回答
3

尊敬的教授，减法应该用加法来定义。我重载了一元“-”运算符并在别处定义了 bignum 加法例程。我正在使用9 的补码来简化/加速加法（不需要讨厌的进位！），并使用基于表格的答案查找（为什么在只有 10 个时计算总和？）。bigNum 减法例程（根据您的规格）如下：

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
    bigSum(N1, -N2, N3);
}
于 2009-08-24T20:47:14.820 回答