Сумма многоразрядных чисел

Алгоритмизация / Сумма многоразрядных чисел

В некоторых случаях у программистов возникает необходимость обработки целых чисел, разрядная сетка которых выходит за пределы, предоставляемые стандартными типами данных int (4 байта) и long int (8 байт).
Такие числа вводятся пользователем в виде текстовой строки и обрабатываются как массив байт. Каждый байт такого числа содержит символ, соответствующий цифре введенного числа.
При этом все арифметические операции с такими числами производятся аналогично выполнению операций сложения, вычитания, умножения, деления в столбик.

О переводе числа из символьной формы в числовую и обратно обсуждалось здесь.
Сложение положительных чисел ведется начиная с младшего разряда в следующем порядке

  • Рассматриваем массивы символов, представляющих числа начиная с конца.
  • Выбираем разряд каждого числа. Если разряд отсутствует, заменяем его нулем.
  • Складываем рассматриваемые разряды чисел.
  • Если сумма превышает 9, фиксируем добавление 1 к следующему разряду и отнимаем 10 от суммы.
  • Переходим к следующему по старшинству разряду чисел
  • Повторяем изложенные выше действия для всех разрядов.

Количество разрядов результата выбирается на 1 больше чем у большего из рассматриваемых чисел.

Реализация

#include <iostream>
using namespace std;
char * sum(char *a, char *b) {
  int lena = strlen(a); // количество разрядов первого числа
  int lenb = strlen(b); // количество разрядов второго числа
  char *c;
  int add = 0; // перенос в следующий разряд
  int k = lena > lenb ? lena : lenb; // количество разрядов результата
  c = new char[k + 2];
  k++;
  c[k] = '\0'; // завершающий нуль-символ результата
  k--;
  for (int i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--) {
    char dig1 = i < 0 ? 0 : a[i] - ′0′; // если разряд отсутствует, взять 0
    char dig2 = j < 0 ? 0 : b[j] - ′0′; // иначе преобразовать символ в цифру
    char dig = dig1 + dig2 + add; // сложить две цифры разрядов и перенос
    if (dig > 9) { // если сумма разрядов >9
      dig = dig - 10; // отнять 10
      add = 1; // и сгенерировать перенос в следующий разряд
    }
    else add = 0; // переноса нет
    c[k] = dig + '0'; // преобразовать цифру в символ
    k--; // перейти к следующему разряду
  }
  if (add == 0) return &c[1]; // в старшем разряде результата пусто
  else {
    c[k] = add + '0'; // заполнить старший разряд результата
    return c;
  }
}
int main() {
  char a[1000] = { 0 };
  char b[1000] = { 0 };
  cout << "a = ";
  cin.getline(a, 1000);
  cout << "b = ";
  cin.getline(b, 1000);
  cout << a << "+" << b << "=" << sum(a,b) << endl;
  cin.get();
  return 0;
}

Результат выполнения

2016-04-27_16-12-07 2016-04-27_16-12-47

Назад

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *