Песни о Паскале - [100]

Итак, сложение чисел начинаем с младшего, то есть крайнего правого разряда. Если сумма двух цифр превысит девять, то в разряд результата записываем остаток от деления этой суммы на 10 (то есть цифры от 0 до 9), а к следующему разряду добавляем перенос.

Если обозначить складываемые цифры буквами A и B, то алгоритм сложения «в столбик» для одного разряда с учетом предыдущего переноса запишется так:

      цифра := (A + B + перенос) mod 10
      перенос := (A + B + перенос) div 10

Напомню, что операция MOD вычисляет остаток от деления одного целого числа на другое, а операция DIV – частное с отбрасыванием остатка. Перед сложением самого младшего разряда перенос берётся равным нулю. Обратите внимание, что условный оператор здесь излишен.

Великая стройка

Уловив основную идею – действия «в столбик», – программисты задумались над хранением цифр огромного числа. Они рассмотрели два равно подходящих средства: либо массив байтов, каждый из которых будет содержать числа от 0 до 9, либо массив символов «0»…«9». Ученые остановились на символах, но от строки отказались, поскольку строка вмещает лишь 255 символов, а им требовалось больше.

В итоге объявление сверхбольшого числа получилось таким, как показано в программе «P_46_1», – она была написана для отладки процедуры распечатки сверхбольшого числа.

{ P_46_1 – Распечатка сверхбольших чисел }
      { объявления для сверхбольшого числа }
const CSize = 500; { размер массива для цифр }
type TBigNumber = array [1..CSize] of char;
var BN : TBigNumber; { очень большое число! }
      { Процедура распечатки сверхбольшого числа
      Младшие цифры числа располагаются в младших элементах массива.
      Но распечатывать надо, начиная со старших цифр.
      Поэтому обработку массива ведем от конца к началу.
      При этом старшие позиции, заполненные пробелами, не печатаем.}
procedure WriteBigNumber(var F: text; const aNum: TBigNumber);
var i : integer;
begin
i:= SizeOf(aNum); { печать начинаем со старших цифр }
{ Пока встречаются незначащие цифры, пропускаем их }
while (i>0) and not (aNum[i] in ['1'..'9']) do Dec(i);
{ Если весь массив заполнен пробелами, то печатаем ноль }
if i=0 then Write(F, '0');
{ Теперь печатаем оставшиеся цифры }
while i>0 do begin
      Write(F, aNum[i]);
      Dec(i);
end;
{ Добавляем ещё одну пустую строчку для удобства созерцания }
Writeln(F); Writeln(F);
end;
var i : integer;
begin       { === Главная программа === }
FillChar(BN, SizeOf(BN), ' '); { заполняем пробелами }
WriteBigNumber(Output, BN);
FillChar(BN, SizeOf(BN), '7'); { заполняем семерками }
WriteBigNumber(Output, BN);
{ заполняем случайными цифрами }
for i:=1 to CSize-1 do BN[i]:= Char(Random(100) mod 10 + Ord('0'));
WriteBigNumber(Output, BN);
Readln;
end.

Итак, тип данных TBigNumber – это сверхбольшое число в виде массива из 500 цифр. Процедура WriteBigNumber – печать сверхбольшого числа – выполняет то, о чем говорит её название. Напомню, что примененная здесь процедура Dec(i) выполняет быстрое вычитание единицы.

В главной программе вы найдете процедуру FillChar – «заполнить символом». Для заполнения массива можно организовать цикл, но процедура FillChar делает это проще и быстрее, она объявлена в Паскале так:

      procedure FillChar(var X; Count: Integer; Value: Byte);

Обратите внимание, что тип первого параметра X не указан, что крайне редко для Паскаля! По сути это ссылка на переменную любого типа. Второй параметр – Count – задает количество байтов, помещаемых в переменную X. Обычно значение Count совпадает с размером этой переменной и задается равным SizeOf(X). И, наконец, третий параметр Value – «значение», тоже не совсем обычен. Его тип объявлен как байт (то есть число), но в действительности может принимать любой однобайтовый тип данных, например, символ или булево значение. Вот несколько примеров.

var A : array 1..100 of char;
      B : array 1..200 of byte;
      С : array 1..50 of boolean;
...
      FillChar(A, SizeOf(A), ’*’);       { заполнение массива звездочками }
      FillChar(B, SizeOf(B), 0);       { заполнение массива нулем }
      FillChar(C, SizeOf(C), false); { заполнение массива «ложью» }

Согласитесь, нелегко отказаться от применения столь удобной процедуры.

И последнее. В нашу процедуру WriteBigNumber передается ссылка на выходной файл, что придает ей универсальность. Вызывая её из главной программы, мы передаём туда файловую переменную Output, – это файл, связанный с экраном. Напомню, что файл Output не требует ни объявления, ни открытия, ни закрытия – он встроен в язык готовеньким. Существует и встроенный файл по имени Input – он служит для ввода данных с клавиатуры.

Длинная арифметика

Итак, испытав рассмотренную нами программу, королевские программисты сделали первый шаг к своей цели – освоили распечатку сверхбольших чисел. Теперь предстояло написать процедуру для сложения таких чисел, ей дали имя AddNumbers – «сложить числа». Она принимает два параметра – это ссылки на сверхбольшие числа, то есть на массивы. Работа процедуры основана на формулах сложения в столбик, причем младшей цифрой числа был выбран первый элемент массива.