Рис.101 – Схема сортировочной горки
Как сортируют состав? Основную работу выполняют двое: сцепщик и стрелочник (который всегда виноват!). От стоящего на горке состава сцепщик отсоединяет по очереди вагон за вагоном и сообщает стрелочнику по рации, в который из тупиков направить очередной вагон, – тому остается лишь переводить свои стрелки. Вкатившись в тупик, вагон тормозится земляным валом или слегка соударяется с уже стоящим там вагоном и автоматически сцепляется с ним. «Разбросав» по тупикам один состав, на горку выкатывают другой и продолжают сортировку, пока в тупиках не сформируются новые составы, готовые к дальнейшему пути.
Наша цель: смоделировать сортировочную горку, то есть создать программу, ведущую себя подобно такой горке. Вагоны заменим символами; следовательно, и состав и стоящие в тупиках вагоны мы представим строками. Будем считать первый символ строки первым вагоном состава, – он прицеплен к локомотиву. В тупике первым будет вагон, стоящий у земляного вала. Легко догадаться, что обрабатывать вагоны будем по принципу стека, поскольку сцепщику всегда доступен только последний вагон.
Договорившись об этом, сформулируем задачу окончательно. Дана строка символов (состав), из которой надо сформировать три других. Вагоны, обозначенные большими буквами ’A’…’Z’, отправим на станцию «A»; другие, обозначенные маленькими буквами ’a’…’z’, – поедут к станции «B», а третьи, обозначенные цифрами ’0’…’9’, – к станции «C». Программа должна сформировать три строки – это вновь собранные составы. Первый символ в них, – это вагон, прицепленный непосредственно к локомотиву.
Для решения задачи надо всего лишь в точности повторить действия сцепщика и стрелочника. Будем «отцеплять» символы от строки и «заталкивать» их в стеки – это наши тупики. Значит, надо построить механизм для стеков. Он будет похож на механизм для очереди: элементы храним в строковых переменных, а для занесения и извлечения элементов из стека учредим две процедуры. По традиции программисты называют эти процедуры так: Push – затолкнуть в стек, и Pop – вытолкнуть из стека.
Процедура заталкивания в стек Push присоединяет символ к концу строки. Она точь-в-точь повторяет процедуру установки в очередь, только называется иначе.
А функция выталкивания из стека Pop возвращает последний символ строки, одновременно удаляя его оттуда. Если же стек окажется пуст, функция сообщит об этом. Сходство с функцией извлечения из очереди очевидно, разница лишь в позиции извлекаемого символа: для очереди это первый символ, а для стека – последний.
Теперь вам не составит труда разобраться в показанной ниже программе «P_45_2». Обратите внимание на отцепку вагонов от исходного состава: она тоже выполняется функцией выталкивания Pop, поскольку исходный состав трактуется как непустой стек.
{ P_45_2 – Сортировочная станция }
{ Помещение элемента в стек }
procedure Push(var aStack: string; arg: char);
begin
aStack:= aStack + arg; { добавляем в конец строки }
end;
{ Извлечение элемента из стека }
function Pop(var aStack: string; var arg: char): boolean;
begin
if Length(aStack) = 0 { если стек пуст }
then Pop:= false { сообщаем об этом }
else begin
{ возвращаем последний элемент }
arg:= aStack[Length(aStack)];
{ и удаляем его из стека }
Delete(aStack, Length(aStack), 1);
Pop:= true; { признак того, что стек не был пуст }
end;
end;
var S : string; { исходный состав }
SA, SB, SC : string; { три сортировочных тупика A,B,C}
c : char; { очередной вагон }
begin
S:= 'HEjd31kDJK62px912se3BKdwL9'; { Исходный состав }
Writeln('Исходный состав: '+S);
SA:=’’; SB:=’’; SC:=’’; { очистка тупиков }
{ Отцепляем вагоны от исходного состава и заталкиваем в тупики }
while Pop(S, c) do begin
if c in ['A'..'Z'] then Push(SA, c);
if c in ['a'..'z'] then Push(SB, c);
if c in ['0'..'9'] then Push(SC, c);
end;
{ Теперь исходный состав пуст, то есть S='' }
{ Выкатываем вагоны из тупика A и цепляем к первому составу }
while Pop(SA, c) do Push(S, c);
Writeln('На станцию A : '+S);
S:=''; { Освобождаем пути }
{ Выкатываем вагоны из тупика B и цепляем ко второму составу }
while Pop(SB, c) do Push(S, c);
Writeln('На станцию B : '+S);
S:=''; { Освобождаем пути }
{ Выкатываем вагоны из тупика C и цепляем к третьему составу }
while Pop(SC, c) do Push(S, c);
Writeln('На станцию C : '+S);
Readln;
end.
Вы познакомились с механизмами очередей и стеков. Мы построили их на основе символьных строк, но в системном программировании это делается иначе, и скоро вы узнаете об этом больше.
Итоги
• Очереди и стеки – это механизмы, применяемые в системных программах. Элементами очередей и стеков могут быть любые объекты.
• Очередь обслуживает элементы по принципу «первый пришел – первый ушел» или сокращенно FIFO (First-In, First-Out).
• Стек обслуживает элементы по принципу «последний пришел – первый ушел» или сокращенно LIFO (Last-In, First-Out).
А слабо?
А) Исследуя модель танцевального кружка, можно заметить, что в любой момент одна из двух очередей обязательно пуста. В самом деле, если приходит больше мальчиков, то будет пуста девчоночья очередь и наоборот. Можно ли обойтись одной очередью? Придумайте, как это сделать.
Подсказка: добавьте функцию для тестирования очереди с тем, чтобы выяснить, не пуста ли она. И, если не пуста, то кто томится в ней – мальчик или девочка? Эта функция не должна изменять состояние очереди.
Б) На реальных станциях на горку последовательно загоняют несколько составов, а уж потом освобождают тупики. Добавьте в модель сортировочной горки возможность такой обработки. Исходные составы (строки) должны вводиться с клавиатуры, признак окончания ввода – пустая строка. Совет: выделите действия по сортировке одного состава в отдельную процедуру.
В) Постройте механизмы очереди и стека на базе массива символов, а не на базе строки. Какие дополнительные переменные здесь понадобятся?
Глава 46
Огромные числа
Давно минули времена, когда для счета всем хватало своих пальцев – первого «калькулятора» человечества, а наши потребности в счете все растут и растут…
Сколько звезд на небе?
Некий король – любитель науки, порядка и немножко чудак – распорядился пересчитать все, что ни есть, в своих владениях. Ладно бы, его интересовали крупные предметы вроде домов, машин и всего такого… Но нет, король велел пересчитать и капли в морях, и песчинки на берегах, и травинки в степях! Пока ученые придумывали способы подсчета, программисты возились с другой задачей – обработкой всего этого на компьютере. Они искали подходящий тип данных для хранения тех огромных чисел, что нужны ученым! Обратившись к описанию языка Паскаль, программисты заинтересовались двумя числовыми типами, которые на первый взгляд подходили для такого случая.
Первый из них – тип LongInt – длинное целое число. Наибольшее значение для этого типа чисел составляет 2'147’483’647, то есть несколько больше двух миллиардов. Маловато будет, – рассудили мудрецы, и продолжили поиск.
