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

Writeln('На станцию C : '+S);

Readln;

end.

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

Итоги

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

• Очередь обслуживает элементы по принципу «первый пришел – первый ушел» или сокращенно FIFO (First-In, First-Out).

• Стек обслуживает элементы по принципу «последний пришел – первый ушел» или сокращенно LIFO (Last-In, First-Out).

А слабо?

А) Исследуя модель танцевального кружка, можно заметить, что в любой момент одна из двух очередей обязательно пуста. В самом деле, если приходит больше мальчиков, то будет пуста девчоночья очередь и наоборот. Можно ли обойтись одной очередью? Придумайте, как это сделать.

Подсказка: добавьте функцию для тестирования очереди с тем, чтобы выяснить, не пуста ли она. И, если не пуста, то кто томится в ней – мальчик или девочка? Эта функция не должна изменять состояние очереди.

Б) На реальных станциях на горку последовательно загоняют несколько составов, а уж потом освобождают тупики. Добавьте в модель сортировочной горки возможность такой обработки. Исходные составы (строки) должны вводиться с клавиатуры, признак окончания ввода – пустая строка. Совет: выделите действия по сортировке одного состава в отдельную процедуру.

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

Глава 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 – частное с отбрасыванием остатка. Перед сложением самого младшего разряда перенос берётся равным нулю. Обратите внимание, что условный оператор здесь излишен.

Великая стройка