Сложение очень длинных целых чисел

Задача

Вводятся два очень длинных целых числа. Найти их сумму. Под "очень длинными целыми числами" здесь подразумеваются такие, которые не помещаются даже в самый большой по диапазону целочисленный тип данных.

Решение

Описание переменных:

  • s1, s2, s3 - строковые представления первого, второго числа и их суммы;
  • n1, n2, n3 - текущие разряды первого и второго чисел и перенос из предыдущего разряда;
  • l1, l2 - длины введенных строк из чисел;
  • c - строковое представление суммы текущих разрядов.

Алгоритм решения задачи:

Вводятся два числа, которые записываются в программу как строки. Измеряется длина строк. В случае, если первая строка длиннее второй, переменные обмениваются значениями. Это делается для избежания сложностей в дальнейшем.

В цикле символы строки s1 перебираются с конца до первого (счетчик i). Каждый символ преобразуется в целое число. Также с конца берутся символы s2 (счетчиком служит l2) и преобразуются в целое. Числа складываются. Сумма записывается в начало строки s3 без старшего разряда, который сохраняется в отдельной переменной n3 и добавляется к сумме при следующем сложении разрядов.

Когда строка s1 заканчивается, надо проверить есть ли перенос из младшего разряда. Если есть, надо продолжать складывать, пока перенос не станет равным нулю.

После того, как складывать уже нечего, надо дописать впереди s3 оставшуюся часть s2.

Программа на языке Паскаль:

var 
    s1, s2, s3: string;
    n1, n2, n3, l1, l2, l3, i: byte;
    c: string[1];
 
begin
    readln(s1);
    readln(s2);
    l1 := length(s1);
    l2 := length(s2);
    if l1 > l2 then begin
        s3 := s1; l3 := l1;
        s1 := s2; l1 := l2;
        s2 := s3; l2 := l3;
    end;
 
    s3 := ''; n3 := 0;
    for i := l1 downto 1 do begin
        val(s1[i], n1);
        val(s2[l2], n2); 
        l2 := l2 - 1;
        str((n1 + n2 + n3) mod 10, c);
        s3 := c + s3;
        if n1 + n2 + n3 > 9 then 
            n3 := 1
        else n3 := 0;       
    end;
 
    while n3 = 1 do begin
        if l2 <> 0 then begin
            val(s2[l2], n2); 
            l2 := l2 - 1;
            str((n2 + n3) mod 10, c);
            s3 := c + s3;
            if n2 + n3 < 10 then 
                n3 := 0;
        end
        else begin
            s3 := '1' + s3;
            n3 := 0;
        end;
    end;
 
    if l2 <> 0 then
        s3 := copy(s2, 1, l2) + s3;
 
    writeln(s3);
end.

Пример выполнения программы:

0000004376576453756
2736472346246724644
2736476722823178400

Комментарии

var
  s1, s2, s0: String;
  n1, n2, c: Integer;
begin
  WriteLn('ПРОГРАММА СЛОЖЕНИЯ ДВУХ БОЛЬШИХ НАТУРАЛЬНЫХ ЧИСЕЛ');
  // вводим две строки больших чисел
  Write('Введите первое число: ');
  ReadLn(s1);
  Write('Введите второе число: ');
  ReadLn(s2);
  // делаем "числа" (строки) одинаковой длины, "приклеивая" к короткому "числу" вначале нули
  // например, ввели числа 1578992231 и 254
  // после выполнения этого цикла "числа" примут вид:
  // 1578992231 и 0000000254
  // по 10 цифр в каждом числе
  while Length(s1)<>Length(s2) do
    if Length(s1)<Length(s2)
      then s1:= '0' + s1
      else s2:= '0' + s2;
  // эта переменная накапливает дополнительный разряд
  // (то, что "держим в уме", когда складываем числа столбиком)
  c:= 0;
  // очищаем строку результата сложения
  s0:= '';
  // складываем поразрядно справа налево два числа одинаковой длины
  while Length(s1)>0 do begin
    // получаем из "чисел" последние "цифры" и переводим их в числовой тип
    n1:= StrToInt(s1[Length(s1)]);
    n2:= StrToInt(s2[Length(s2)]);
    // складываем эти две цифры, учитывая то, что "держим в уме"
    // и "приклеиваем" их сумму (одну цифру) слева к строке результата
    s0:= IntToStr((n1 + n2 + c) mod 10) + s0;
    // если было получено число больше 10 - "запоминаем" его десяток в переменной c
    c:= (n1 + n2 + c) div 10;
    // обрезаем последние "цифры" у обоих "чисел", которые сложили
    Delete(s1, Length(s1), 1);
    Delete(s2, Length(s2), 1);
    // если сложили все разряды и то, что "держим в уме", больше ноля -
    // приклеиваем это к началу строки результата
    if (Length(s1)=0)and(c>0)
      then s0:= IntToStr(c) + s0;
  end;
  WriteLn('Сумма этих чисел = ', s0);
end.