Вскоре они наткнулись на другой тип чисел – Extended, который мог вмещать сказочные значения – вплоть до 104932! Иначе говоря, эти числа могли содержать почти пять тысяч цифр! Но радость математиков была недолгой; рассмотрев тип Extended пристальней, они отвергли его. Оказалось, что из этих пяти тысяч цифр только первые двадцать – точные (их называют значащими), а остальные не внушают доверия, и могут быть замены чем угодно, хоть нулями.
Есть ли толк от этих неточных чисел? Есть. Дело в том, что в инженерных и научных расчетах этой точности вполне хватает. Но здесь был иной случай, – требовался абсолютно точный подсчет, государь не терпел огрехов. «Точность – вежливость королей!» – говаривал он. И программисты ткнулись, как обычно, в тупик.
Сложение «в столбик» никто не отменял
Выход из тупика нашелся случайно. Один из королевских программистов помогал сынишке справиться со школьными уроками – складывали числа «в столбик». Тут его и осенило: почему бы и нам, – смекнул папаша, – не складывать числа тем же способом? Так тряхнем стариной и вспомним это сложение «в столбик»? Рис. 102 освежит вашу память.
Рис.102 – Пример сложения в столбик
Итак, сложение чисел начинаем с младшего, то есть крайнего правого разряда. Если сумма двух цифр превысит девять, то в разряд результата записываем остаток от деления этой суммы на 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 – «сложить числа». Она принимает два параметра – это ссылки на сверхбольшие числа, то есть на массивы. Работа процедуры основана на формулах сложения в столбик, причем младшей цифрой числа был выбран первый элемент массива.
Поскольку массив содержит символы ’0’…’9’, а не числа 0…9, при сложении символы преобразуем в числа и обратно (ведь символы складывать нельзя). Эти простые превращения выполняем по формулам.
цифра := Ord (символ_цифры) – Ord (’0’)
символ_цифры := Char (Ord (’0’) + цифра)
Вот эта чудесная программа целиком.
{ P_46_2 – Сложение сверхбольших чисел }
const CSize = 500; { размер массива }
{ объявление типа для сверхбольшого числа }
type
TBigNumber = array [1..CSize] of char;
