Песни о Паскале (СИ)

Текст добавлен: 6 ноября 2017, 03:30

Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

Жанр:

Драматургия

сообщить о нарушении

Текущая страница: 18 (всего у книги 29 страниц)

В) Постройте механизмы очереди и стека на базе массива символов, а не на базе строки. Какие дополнительные переменные здесь понадобятся?

Глава 46

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

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

Сколько звезд на небе?

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

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

Вскоре они наткнулись на другой тип чисел – Extended, который мог вмещать сказочные значения – вплоть до 10⁴⁹³²! Иначе говоря, эти числа могли содержать почти пять тысяч цифр! Но радость математиков была недолгой; рассмотрев тип 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;

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). Если же первые буквы фамилий совпадали, то книгу все равно листали заново, поэтому на «БББ» тратилось шесть часов. Создайте функцию, принимающую «очередь посетителей» – строку из больших латинских букв – и возвращающую время, необходимое для выдачи всех справок.

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

Глава 47

Системы счисления

Эта глава промчит нас дорогой, по которой человечество брело несколько тысячелетий, – мы научимся изображать числа.

Из тьмы веков

Когда явилась потребность в счете? – никто не помнит этого, но мудрецы всех времен упорно искали удобные способы изображения чисел. Поиск систем счисления – так их теперь называют – это захватывающая история! Трудно поверить, но античные математики ещё не знали десятичной системы! И как они решали свои замысловатые задачи?

Первой системой счисления была, очевидно, единичная. Тогда некоторому количеству одних предметов сопоставляли такое же количество других (камушков, ракушек или зарубок на дереве). Что тут скажешь? – каменный век! Изображать большие числа в этой системе немыслимо.

Потребовались века, чтобы индийцы додумались до цифр. Их цифры были похожи на современные «1», «2», «3» и так далее. Но истинную революцию в арифметике содеяла цифра «0». Тот, кто её придумал, поставил все на свои места, причем в буквальном смысле. Ведь ноль породил позиционную десятичную систему счисления, где «вес» цифры определяется её позицией внутри числа. Странно, что в просвещенной Европе удобная десятичная система приживалась непросто и вытеснила неудобную римскую только в 15-16 веках!

Наконец пробил час немецкого математика Лейбница, в голову которого пришла здравая мысль: «Зачем так много цифр? – изумился он, взглянув на циферблат своих часов, – когда вполне достаточно двух!». Так была изобретена двоичная система счисления, – «родная» для нынешних компьютеров.

Число и его изображение

Пора прояснить, что же такое системы счисления? Числа – это плод нашего воображения, в природе их никто не видел, они существуют лишь в наших головах. Не потому ли с числами связаны порой курьезные заблуждения? Иные полагают, что перевод числа из одной системы счисления в другую меняет это число. Вам смешно? Взгляните на рис. 103, где устроилась дюжина попугаев. Дюжина – это двенадцать, я написал это по-русски, а мог бы на другом языке. Или обозначил бы китайским иероглифом, – количество попугаев от этого не изменится. Как в поговорке: хоть горшком назови, только в печь не сажай!

Рис.103 – Способы изображения числа 12

Итак, что ни скажи, но на картинке все те же двенадцать попугаев. Это число изображено рядом в нескольких системах счисления: единичной, десятичной, двоичной и шестнадцатеричной. И, хотя изображения не схожи меж собой, все они относятся к двенадцати попугаям. Стало быть, число и его изображение – не одно и то же!

Мы изображаем числа строками символов – цифрами. Поручив процедуре Writeln напечатать число, мы не задумываемся, как она делает это, – число превращается в строку цифр неведомым нам образом. Допустим на минуту, что процедура Writeln этого не умеет, и тогда явится потребность сделать такое преобразование самим. Итак, ставим себе первую задачу: преобразовать число в строку, то есть получить символьное изображение числа.

Справившись с первой задачей, займемся обратным преобразованием – строки в число. Это умеет процедура Readln, но мы пока забудем об этом. Дело в том, что упомянутые стандартные процедуры понимают лишь десятичную систему счисления. Мы же добиваемся большего, – мы хотим изображать числа в любой системе счисления (двоичной, троичной и так далее). А начнем, разумеется, с родной десятичной системы.

Десятичная система

Десятичную систему знает всякий: здесь крайняя правая цифра числа означает единицы, а последующие – десятки, сотни и так далее. Например, число 2048 представляется так:

2048 = 2 • 1000 + 0 • 100 + 4 • 10 + 8 • 1

Или так:

2048 = 2 • 10³ + 0 • 10² + 4 • 10¹ + 8 • 10⁰

То есть, позиция цифры в числе равна показателю степени при десятке, если счет позиций вести справа налево, начиная с нуля.

Повторю нашу цель: мы хотим превратить нечто цельное – число – в цепочку символов. Как это сделать? Есть мысли? Я предлагаю «откалывать» от числа цифру за цифрой, превращая их в символы и складывая в строку. Из опыта известно, что легче всего «отгрызть» от числа младшую цифру, вычисляя остаток от деления на десять, вот так:

младшая_цифра := число MOD 10

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

старшая_часть := число DIV 10

Так прояснилась схема дробления числа, показанная на рис. 104.

Рис.104 – Выделение отдельных цифр десятичного числа

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

var N : integer; S : string;

begin { Преобразование числа в строку десятичных цифр }

Write('N= '); Readln(N);

S:='';

repeat

S:= Char((N mod 10)+Ord('0')) + S; { выделение очередной цифры }

N:= N div 10; { отделение старшей части }

until N=0;

Writeln(S); Readln;

end.

Теперь, когда мы смогли превратить число в строку, займемся обратным превращением – соберем число из символов строки. Откуда подступиться к этой сборке? Запишем разложение числа с помощью скобок следующим образом:

2048 = 2 • 1000 + 0 • 100 + 4 • 10 + 8 • 1 = (((0 •10+2) •10+0) •10+4) •10+8

Правила действий со скобками требуют начать вычисление с внутренних, самых глубоких скобок. Следовательно, сборку числа из отдельных цифр начнем со старших разрядов, последовательно умножая накопленную сумму на 10. Внутри самых глубоких скобок добавлено слагаемое 0•10. Не влияя на результат вычислений, оно придает общность алгоритму сборки, который показан на рис. 105.

Рис.105 – Сборка числа из строки десятичных цифр

Например, для числа 2048 сборка пойдет в таком порядке:

N = 0 – исходное значение

N = 0 • 10 + 2 = 2

N = 2 • 10 + 0 = 20

N = 20 • 10 + 4 = 204

N = 204 • 10 + 8 = 2048

А вот программа, работающая по этому алгоритму.

var N : integer; i : integer; S : string;

begin

Write('S= '); Readln(S);

N:=0;

for i:=1 to Length(S) do N:= 10*N + Ord(S[i]) – Ord ('0');

Writeln(N); Readln;

end.

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

Двоичная система

«Отец» двоичной системы Лейбниц не помышлял о великом будущем своей придумки, и на долгие годы о ней забыли. Но изобретатели компьютеров вспомнили. Все компьютеры – от первых моделей до самых современных – строятся из простейших элементов памяти – триггеров. Триггер – это электронная схема с двумя устойчивыми состояниями. Подобие триггера – комнатный выключатель, что может (если исправен) находиться в двух устойчивых состояниях: «включен» и «отключен». То есть, выключатель «помнит» состояние, в которое его привели в последний раз, и является элементом памяти.

Итак, элементы памяти с двумя состояниями – триггеры – составляют основу компьютеров (и почему их не назвали «дваггерами»?). Одно из состояний инженеры обозначили числом 0, а другое – 1. Стало быть, триггер способен «помнить» одно из этих чисел. Маловато для серьезного счета, не так ли? Тогда и вспомнили о двоичной системе Лейбница. Инженеры соединили несколько триггеров в цепочку и назвали эту «гирлянду» регистром. Каждый триггер в регистре, подобно цифрам в десятичном числе, обладает своим весом. В зависимости от позиции в регистре, вес триггера может составлять 1, 2, 4, 8 и так далее, – это степени числа 2. Например, число 12 изображается в двоичной системе так (рис. 106).

Рис.106 – Изображение числа 12 в двоичной системе

Сравните эту кодировку с десятичной системой, – принцип тот же, только веса разрядов другие. Если в десятичной системе вес очередного разряда вдесятеро больше предыдущего, то в двоичной системе – вдвое. Числа, хранящиеся в триггерах (0 или 1) служат множителями этих весов. Таким образом, при достаточной длине регистра в двоичной системе можно изобразить сколь угодно большое число.

Договоримся о форме записи двоичных чисел, иначе путаницы не избежать. У программистов приняты две формы: к символам двоичного изображения добавляют либо суффикс «B» (от Binary – «двоичный»), либо маленькую двоечку. Например, число 12 в двоичной системе записывается так:

1100B или 1100b или 1100₂

А иначе эту запись можно понять как «тысяча сто» в десятичной системе.

Шестнадцатеричная система

Компьютеры никогда не жаловались на двоичную систему, она их вполне устраивает. Сетовать стали программисты, – уж очень громоздкой получалась запись сравнительно небольших чисел, например:

4005 = 111110100101₂

А если программистам несподручно, они что-нибудь придумают. Придумка была простой: двоичную запись разбили на группы по четыре двоичных цифры в каждой – тетрады (от греческого слова Tetra – «четыре»). И каждую тетраду записали в привычной для людей десятичной системе, разделяя тетрады точками. Например, десятичное число 4005 преобразили так:

4005 = 111110100101₂–> 1111.1010.0101₂ –> 15.10.05

Тетрады могут содержать числа от 0 до 15 – всего получается 16 значений, потому систему назвали шестнадцатеричной. Со временем запись сделали ещё короче, заменив числа от 10 до 15 буквами латинского алфавита:

A=10

B=11

C=12

D=13

E=14

F=15

Тогда показанная выше запись преобразилась так: 15.10.05 –> FA5

Рис. 107 показывает это наглядней.

Рис.107 – Преобразование двоичного числа в шестнадцатеричное

Шестнадцатеричную запись можно спутать с десятичной, и даже принять за слово, поскольку в ней встречаются буквы. Потому для таких чисел учредили свои правила: шестнадцатеричная запись числа должна начинаться с цифры, а завершаться суффиксом «H» (от Hexadecimal, Hex – «шестнадцатеричный»). Значит, изобразить число FA5 правильней так:

0FA5H или 0FA5h

Применяют и другие формы записи шестнадцатеричных чисел. Так, в языке Си принята приставка «0x» (0xFA5), а в Паскале начинают с приставки «$» – это знак доллара ($FA5). В таких записях лидирующий ноль не требуется, но для лучшего восприятия указывают обычно две, четыре, либо восемь цифр (в зависимости от величины числа или разрядности данных), например:

12 = 0x0C = $0C <– байт (byte)

4005 = 0x0FA5 = $0FA5 <– слово (word)

4005 = 0x00000FA5 = $00000FA5 <– длинное слово (longint)

Чем хороша шестнадцатеричная система? Легкостью перевода чисел в двоичную систему и обратно. После небольшой тренировки любой может сделать это в уме. При переводе в двоичную систему заменяем каждую шестнадцатеричную цифру четырьмя двоичными и «склеиваем» эти тетрады между собой. И, хотя компьютеры по-прежнему работают в двоичной системе, программисты дружно перешли на шестнадцатеричную. Вот таблица для перевода небольших чисел из одной системы в другую.

Табл. 11 – Изображения чисел в различных системах счисления

Десятичная

Двоичная

16-ричная

Десятичная

Двоичная

16-ричная

0000

1000

0001

1001

0010

1010

0011

1011

0100

1100

0101

1101

0110

1110

0111

1111

Другие системы счисления

Итак, мы познакомились с тремя позиционными системами счислений: десятичной, двоичной и шестнадцатеричной. Существуют ли другие системы? Конечно! Во всех позиционных системах вес цифры определяется её положением в числе, сравните.

2048 = 2 • 10³ + 0 • 10² + 4 • 10¹ + 8 • 10⁰ – десятичная;

12 = 1100₂ = 1 • 2³ + 1 • 2² + 0 • 2¹ + 0 • 1⁰ – двоичная;

4000 = $FA0 = F • 16²+ A • 16¹+ 0 • 16⁰ – шестнадцатеричная.

Число, на котором построена система, называют её основанием. Можно выдумать столько систем счисления, сколько существует чисел, то есть, бесконечно много. Пока нам достаточно тех, что придуманы. А если с других планет прилетят существа с семью пальцами на руках? Для них, вероятно, «родной» будет семеричная система, и мы должны быть готовы к этому!

Так мы подошли к задаче по настоящему серьезной: изобразить число в некоторой системе счисления (основания систем ограничим числами от 2 до 16).

Изображение числа в заданной системе счисления

Преобразуя числа в десятичную систему, мы «отгрызали» цифры, начиная с младших разрядов, операциями деления и получения остатка. Точно так же преобразуют числа и в другие системы, только откалывают куски иного размера. Поскольку в двоичной системе есть только две цифры, то для неё младшая цифра отсекается операцией MOD 2, а старшая часть – операцией DIV 2. Для шестнадцатеричной системы – соответственно операциями MOD 16 и DIV 16. Отсюда следует правило: для преобразования числа в N–ричную систему счисления младшую цифру отделяют операцией MOD N, а старшую часть числа – операцией DIV N.

В программе «P_47_1» функция ConvertFromNumber – «преобразовать из числа» – делает именно то, о чем сказано выше. Обратите внимание на строковую константу.

const CDigits : string = '0123456789ABCDEF';

Она служит для изящного преобразования чисел 0–15 в шестнадцатеричные цифры «0»–«F». Константы, для которых явно указан тип, называют типизированными, – это пример такой константы.

{ P_47_1 – Преобразование в произвольную систему счисления }

{ Функция преобразования десятичного числа в другие системы счисления }

function ConvertFromNumber(aBase, aNumber : integer): string;

const CDigits : string = '0123456789ABCDEF';

var n : integer; c : char; S : string;

begin

S:=''; { Накопитель цифр }

repeat

n:= aNumber mod aBase; { остаток от деления на основание }

aNumber:= aNumber div aBase; { частное от деления на основание }

c:= CDigits[1+n]; { выбираем цифру из строки }

S:= c + S; { вставляем цифру в результат }

until aNumber=0;

ConvertFromNumber:= S; { готово! }

end;

var B, N : integer; { B – основание системы, N – число }

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

repeat

Write('Основание системы= '); Readln(B);

if B in [2..16] then begin

Write('Преобразуемое число= '); Readln(N);

Writeln(ConvertFromNumber(B, N));

end

until not (B in [2..16]);

end.

Эта простая программа подарит вам счастье наблюдать знакомые десятичные числа в экзотических системах счисления, например, в троичной или пятеричной.

Обратное преобразование

Теперь займемся обратной задачей: пусть дана строка символов, изображающая некое число в известной системе счисления; требуется преобразовать эту строку в число и напечатать в десятичной системе.

Сборка числа из десятичных цифр нами освоена. Она выполнялась умножением накопленной суммы на десять с прибавлением очередной цифры, начиная со старшей. Надо ли объяснять, что сборка в других системах выполняется точно так же? Только умножать будем не на десять, а на основание системы счисления. В следующей ниже программе сборка выполняется функцией ConvertToNumber – «преобразовать в число».

{ P_47_2 – Преобразование из других систем счисления }

function ConvertToNumber(aBase: integer; aNumber: string): integer;

var i,n, Sum : integer;

c : char;

begin

Sum:=0; { Накопитель результата }

for i:=1 to Length(aNumber) do begin

c:= Upcase(aNumber[i]);

if c in ['0'..'9']

then n:= Ord(c)-Ord('0') {0..9}

else n:= 10+Ord(c)-Ord('A'); {10..15}

Sum:= aBase*Sum + n; { Накопление суммы }

end;

ConvertToNumber:= Sum; { готово! }

end;

var B : integer; { Основание системы }

N : string; { Изображение числа в виде строки }

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

repeat

Write('Основание системы= '); Readln(B);

if B in [2..16] then begin

Write('Преобразуемое число= '); Readln(N);

Writeln(ConvertToNumber(B, N));

end

until not (B in [2..16]);

end.

Как обычно, здесь выделены операторы, стоящие внимания. Функция UpCase преобразует строчные латинские буквы в заглавные. Ведь шестнадцатеричные цифры от «A» до «F» могут быть введены пользователем в любом регистре, а последующие операторы преобразования цифры в число предполагают заглавные буквы – вот потому и понадобилась функция UpCase.

Назад к карточке книги "Песни о Паскале (СИ)"