Вычитание большого числа в C - PullRequest
Новая
       22

Вычитание большого числа в C

5 голосов
/ 23 августа 2009

Я только что закончил свой экзамен на вводном курсе С около 20 минут назад. Первый вопрос на экзамене застал меня врасплох и заключался в том, чтобы найти разницу в двух больших числах.

Целью было взять две структуры (N1 и N2) по значению и сохранить разницу в структуре, переданной по ссылке (N3). Нам разрешили предположить, что N3 был инициирован со всеми нулями. Максимальный размер может быть любым, поэтому решение все равно должно работать, если числа превышают 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.

Никакие побитовые операторы не должны использоваться, на всякий случай.

Ответы [ 3 ]

10 голосов
/ 23 августа 2009

Задача 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;

(плюс немного больше хлопот, чтобы применить ту же логику и к десятичным цифрам.)

Похоже, у вас была правильная идея, и, возможно, вы просто переосмыслили реализацию?

5 голосов
/ 23 августа 2009

Это должно работать, если 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);
    }
}
3 голосов
/ 25 августа 2009

Уважаемый профессор, вычитание должно быть определено в терминах сложения. Я перегружал унарный оператор "-" и определил подпрограмму добавления bignum в другом месте. Я использую 9 в качестве дополнения , чтобы упростить / ускорить добавление (не надоедать, не нужно!) С помощью поиска ответов на основе таблицы (зачем вычислять суммы, когда их всего 10?) Далее следует процедура вычитания bigNum (согласно вашим спецификациям): 

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
    bigSum(N1, -N2, N3);
}
...