Песни о Паскале — страница 68 из 112

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

Итоги

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

• Встроенная процедура 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+