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