Сложение двух длинных чисел

Сложение двух длинных  чисел

Удобно объявить тип длинных чисел:

type

number =record

len:longword;

digits:array[1..6000] of byte;

end;

Рассмотрим, как длинное  число будет храниться в таком  массиве. В 1 -й ячейке будет храниться  младший разряд числа, то есть единицы, во 2-й ячейке — десятки, в 3-й сотни  и т. д., по одной цифре в каждой ячейке. Если число имеет меньше разрядов, чем numlen, в оставшихся ячейках массива должны храниться нули.

Если необходимый для задачи размер numlen составляет 30 001. Каждое из исходных чисел может иметь до 30 000 разрядов, а результат сложения таких чисел может иметь до 30 001 разряда.

Лучше оформить чтение числа  в качестве отдельной процедуры  с параметром-переменной типа number — тогда в основной программе чтение двух чисел, записанных в двух строках, будет выполнено одинаково, а значит, будет меньше подвержено ошибкам.

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

Теперь об основной части  программы — сложении двух длинных  чисел. Приведем процедуру сложения полностью:

function add(n1. n2 : number):number;

var

i. ls : longword;

begin

  ls:=max(n1.len,n2.len);

  for i := 1 to ls do

    begin

      result.digits[i]:=n1.digits[i]+n2.digits[i]+result.digits[i];

      result.digits[i+1]:=result.digits[i] div 10;

      result.digits[i]:=result.digits[i] mod 10;

    end;

  if result.digits[ls+1]<>0 then inc(ls);

result.len:=ls;

end;

 

Эта функция реализует  сложение двух длинных чисел столбиком. В начале определяем длину наиболее длинного числа и записываем в ls. Затем складываем столбиком как учили в начальной школе. В конце проверяем, не получилось ли ответ длиннее ls, если да – увеличиваем ls на 1.

Длинное произведение

Сама процедура умножения  длинных чисел такова:

for i := 1 to n.len do

    for j := 1 to m.len do

    begin

      result.digits[i+j-1]:=n.digits[i]*m.digits[j]+ result.digits[i+j-1];

      result.digits[i+j]:= result.digits[i+j]+ result.digits[i+j-1] div 10;

      result.digits[i+j-1]:= result.digits[i+j-1] mod 10;

    end;

  ls:= m.len +n.len;

  while (result.digits[ls]=0) and (ls<>1) do

    dec(ls);

result.len:=ls;

 

Эта функция реализует  произведение двух длинных чисел  в столбик. I+j-1 необходимо чтобы было смещение по разрядам. Далее пытаемся определить длину числа в ответе. В худшем случае длина числа будет равняться m.len+n.len. А потом мы уменьшаем ls пока встречаем 0.

Деление длинного числа на короткое

Сама процедура деления  длинного числа на короткое:

mn:=0;

i:=m.len;

lo:=0;

while (mn<n) and (i<>0) do

begin

  mn:=mn*10+m.digits[i];

  dec(i);

end;

while i<>-1 do

begin

inc(lo);

o.digits[lo]:=mn div n;

mn:=mn mod n;

if i=0 then break;

mn:=mn*10+m.digits[i];

dec(i);

if mn<n then

  while (mn<n) and (i<>0) do

  begin

     inc(lo);

    o.digits[lo]:=0;

    mn:=mn*10+m.digits[i];

    dec(i);

  end;

end;

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

В mn хранится остаток от деления. i – позиция текущей цифры в m. lo – позиция текущей цифры в o.

while (mn<n) and (i<>0) do

begin

  mn:=mn*10+m.digits[i];

  dec(i);

end;

Здесь происходит накапливание в mn остатка до тех пор пока mn не станет делиться на n, либо пока цифры в числе m не закончатся.