Песни о Паскале

Глава 46 Огромные числа

Давно минули времена, когда для счета всем хватало своих пальцев – первого «калькулятора» человечества, а наши потребности в счете все растут и растут…

Некий король – любитель науки, порядка и немножко чудак – распорядился пересчитать все, что ни есть, в своих владениях. Ладно бы, его интересовали крупные предметы вроде домов, машин и всего такого… Но нет, король велел пересчитать и капли в морях, и песчинки на берегах, и травинки в степях! Пока ученые придумывали способы подсчета, программисты возились с другой задачей – обработкой всего этого на компьютере. Они искали подходящий тип данных для хранения тех огромных чисел, что нужны ученым! Обратившись к описанию языка Паскаль, программисты заинтересовались двумя числовыми типами, которые на первый взгляд подходили для такого случая.

Первый из них – тип LongInt – длинное целое число. Наибольшее значение для этого типа чисел составляет 2'147’483’647, то есть несколько больше двух миллиардов. Маловато будет, – рассудили мудрецы, и продолжили поиск.

Вскоре они наткнулись на другой тип чисел – Extended, который мог вмещать сказочные значения – вплоть до 10⁴⁹³²! Иначе говоря, эти числа могли содержать почти пять тысяч цифр! Но радость математиков была недолгой; рассмотрев тип Extended пристальней, они отвергли его. Оказалось, что из этих пяти тысяч цифр только первые двадцать – точные (их называют значащими), а остальные не внушают доверия, и могут быть замены чем угодно, хоть нулями.

Есть ли толк от этих неточных чисел? Есть. Дело в том, что в инженерных и научных расчетах этой точности вполне хватает. Но здесь был иной случай, – требовался абсолютно точный подсчет, государь не терпел огрехов. «Точность – вежливость королей!» – говаривал он. И программисты ткнулись, как обычно, в тупик.

Выход из тупика нашелся случайно. Один из королевских программистов помогал сынишке справиться со школьными уроками – складывали числа «в столбик». Тут его и осенило: почему бы и нам, – смекнул папаша, – не складывать числа тем же способом? Так тряхнем стариной и вспомним это сложение «в столбик»? Рис. 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;

var BN1, BN2 : TBigNumber;     { два очень больших числа }

{ Процедура распечатки сверхбольшого числа }

procedure WriteBigNumber(var F: text; const aNum: TBigNumber);

var i : integer;

begin

i:=CSize;

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;

{ Процедура сложения сверхбольших чисел "в столбик".

Результат помещается в первое число, что равносильно оператору сложения

aNum1 := aNum1 + aNum2 }

procedure AddNumbers(var aNum1, aNum2 : TBigNumber);

var i,j : integer;

    n1, n2 : integer;     { слагаемые цифры }

    sum, ovr : integer; { сумма и перенос }

begin

ovr:=0; { в начале переполнение = 0 }

{ цикл по всем цифрам, кроме последней }

for i:=1 to CSize-1 do begin

    j:=i;     { j используется после завершения цикла }

    { Если в текущей позиции пробел, то считаем его нулем,

    а иначе символ цифры преобразуем в цифру 0..9 }

    if aNum1[i]=' '

    then n1:=0

    else n1:=Ord(aNum1[i])-Ord('0'); { n1 = 0..9 }

    if aNum2[i]=' '

    then n2:=0

    else n2:=Ord(aNum2[i])-Ord('0'); { n2 = 0..9 }

    sum:= (n1+n2+ovr) mod 10;     { сумма sum = 0..9 }

    ovr:= (n1+n2+ovr) div 10;     { перенос ovr = 0 или 1 }

    { Преобразуем цифру в символ цифры }

    aNum1[i]:= Char(sum + Ord('0'));

end;

{ Если было переполнение, то за последней цифрой помещаем единицу }

if ovr<>0 then aNum1[j+1]:='1';

end;

var F : text; i : integer;

begin     { === Главная программа === }

Assign(F, ''); Rewrite(F);

FillChar(BN1, SizeOf(BN1), ' '); FillChar(BN2, SizeOf(BN2), ' ');

for i:=1 to CSize-1 do BN1[i]:= Char(Random(100) mod 10 + Ord('0'));

for i:=1 to CSize-1 do BN2[i]:= Char(Random(100) mod 10 + Ord('0'));

WriteBigNumber(F, BN1); { первое слагаемое }

WriteBigNumber(F, BN2); { второе слагаемое }

AddNumbers(BN1, BN2);

WriteBigNumber(F, BN1); { сумма }

Close(F); Readln;

end.

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

Первое слагаемое (499 цифр):

8803447475526346381115774817716923675204013515325625368435081217045581659031800071999794366

1182651825637587203786736601358393989531415129060249427882941568716183991696120939861150054

6931200667866376204115538852965830795649105020542397666292186509678053905826675950787561760

5869708358318344949299824242208000929286578540423001609560508264356930728328745107168941254

6971095113657279669411494318090578430589776576476782988688149478003857089789749459805075709

20442289778748724626014927619547782761770630

Второе слагаемое (499 цифр):

4301056320813339259127743021691072439999265735917637003180047595481028679918094988721008241

5896167531551745866707619828471298816918833129959986427866428281363411295696463579032521755

7777821776772170919033280201619190732499393489224796857416710264662385957326645736202490241

1316796587449679809153393673306802289884085958345033422404931451426067305519212005730606726

2742584874919295598665812780867323280259752302809107360806816867592608963920797222278187770

61923128832709593717254099272079488419978116

Сумма (500 цифр):

1310450379633968564024351783940799611520327925124326237161512881252661033894989506072080260

7707881935718933307049435642982969280645024825902023585574936985007959528739258451889367181

0470902244463854712314881905458502152814849850976719452370889677434043986315332168699005200

1718650494576802475845321791551480321917066449876803503196543971578299803384795711289954798

0971367998857657526807730709895790171084952887928589034949496634559646605371054668208326347

982365418611458318343269026891627271181748746

Результат сложения нетрудно проверить в уме, – здесь калькулятор не только излишен, но и бесполезен.

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

• Встроенная процедура FillChar заполняет нужным значением массив или переменную любого типа.

• Файловые переменные Input (для ввода с клавиатуры) и Output (для вывода на экран) встроены в язык. Они не требуют ни объявления, ни открытия, ни закрытия, и могут передаваться в качестве параметров процедур, как и другие файловые переменные.

А) Постройте сверхбольшие числа на основе строковых переменных (количество цифр – не более 255).

Б) Напишите процедуру для вычитания сверхбольших чисел. Или слабо? Учтите, что разность может быть и отрицательной!

В) Автоматически объявленные файловые переменные Input и Output по умолчанию связаны соответственно с клавиатурой и экраном. Но их можно связать и с дисковыми файлами, например:

    Assign(Input, 'Data.In'); Reset(Input);

    Assign(Output, 'Data.Out'); Rewrite(Output);

    Readln(S);     { Чтение строки из Data.In }

    Writeln(S);     { Запись строки в Data.Out }

    Close(Input); Close(Output);

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

Задачи на темы предыдущих глав

Г) Жители райцентра Бюрократовка дневали и ночевали в очереди за справками. Все потому, что там применяли механический текстовый файл – огромную скрипучую книгу, которая листалась лишь в одном направлении – от начала к концу файла. Если первая буква фамилии очередного посетителя следовала по алфавиту далее, чем у предыдущего, то чиновник продолжал листать страницы с текущей позиции, а иначе открывал на первой и листал от начала. Переход от одной буквы алфавита к другой и возврат в начало занимали один час. Так, если буквы следовали в порядке «АБВ», то на выдачу справок тратилось три часа, а если в обратном порядке – «ВБА», – то шесть часов (3+2+1). Если же первые буквы фамилий совпадали, то книгу все равно листали заново, поэтому на «БББ» тратилось шесть часов. Создайте функцию, принимающую «очередь посетителей» – строку из больших латинских букв – и возвращающую время, необходимое для выдачи всех справок.

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