Песни о Паскале - [96]
Е) Вращение строки влево. Напишите процедуру для перемещения 2-го символа на место 1-го, 3-го – на место 2-го и т.д. Первый символ должен стать последним.
Ж) Строка содержит несколько слов – предложение. Напишите программы для решения следующих задач.
• Напечатать в столбик отдельные слова введённого предложения.
• Определить количество слов в строке.
• Равномерно расставить пробелы между словами так, чтобы удлинить строку до 80 символов (исходная строка короче 80).
З) Напишите булеву функцию, определяющую, является ли строка (параметр) палиндромом. Палиндром читается одинаково в обоих направлениях.
И) Напишите булеву функцию, определяющую, можно ли из букв первого слова составить второе (например, «клавиша» и «вилка» – TRUE). Учитывается только набор букв, а не их количество. Подсказка: примените множества.
К) Дана строка, содержащая не менее трёх символов. Найти в ней три стоящих подряд символа, дающих максимальную сумму своих кодов.
Л) В строке найти возрастающую последовательность символов наибольшей длины (сравнивайте коды символов).
М) Напишите булеву функцию, проверяющую, следуют ли символы строки по неубыванию своих кодов.
Н) Напишите функцию для шифрования строки путём перестановки её символов, расположенных на нечётных позициях: первый символ обменивается с последним, третий – с третьим от конца и т.д.
Глава 45
Очереди и стеки
Хорошей вещи найдется уйма применений. Взять хотя бы строки, из которых мы построим сейчас инструменты системных программистов – очереди и стеки.
Для меня системные программисты – это боги, ступившие на землю (не путайте их с системными администраторами!). Операционные системы, компиляторы, вирусы и антивирусы – это их мозгов дело. Настоящего системщика я видел лишь разок, да и то издали. Таинственное системное программирование! – дерзнем ли коснуться его? Почему нет? Надо же когда-то начинать! Ведь стеки и очереди отчасти вам знакомы.
Переживайте неприятности по мере их поступления – эта житейская мудрость касается любого из нас. Жизнь – это поток событий, барахтаясь в котором, мы поминутно решаем: прервать ли начатое дело и хвататься за другую проблему? Или отложить эту новую проблему «на потом»?
Смотрите: вот компьютер и Вовочка, мирно играющий в «звездные войны». Входит мама: «Вова, ты уроки сделал?». Вова неохотно откладывает игру и приступает к урокам. Через полчаса мама снова беспокоит его: «Вовочка, я не могу отойти от плиты. Сгоняй-ка быстро за луком». Уроки откладываются, и Вова отправляется в магазин. По пути он видит гоняющих мяч приятелей, – им не хватает вратаря. Как не помочь друзьям? Поход в магазин откладывается, и Вовочка на страже ворот. Делу время, а потехе час. Закончилась игра, и можно выполнить мамино поручение. Купив луку, Вова доделывает отложенные уроки и возвращается к первому занятию – «звездным войнам».
Вовочка обрабатывал события по принципу стека, – скажет об этом системный программист. Другое название стека – дисциплина обслуживания LIFO, что значит «Last-In, First-Out», или по-русски: «последним пришел – первым ушел». Мы соприкоснулись со стеком, разбирая рекурсивную процедуру быстрой сортировки. Помните пример с укладкой рюкзака? А вот ещё пример: магазин для патронов. Патрон, вставленный в магазин последним, выстрелит первым, и наоборот.
Итак, пример с Вовочкой показал, что важные события мы обслуживаем по принципу стека.
А очередь? Какое отношение к нам имеет этот символ потерянного времени? Заметив, как «тормозит» порой ваш компьютер, вспомните о ней. Иногда компьютер реагирует на мышку и клавиатуру с заметным опозданием, но не забывает о нажатиях и щелчках. Они накапливаются в очереди, а затем извлекаются оттуда и обрабатываются.
Или другой пример – печатание документов на сетевом принтере. Когда принтер занят, операционная система ставит запросы на печать в очередь. А затем – по мере готовности принтера – выбирает файлы из этой очереди и отправляет принтеру.
За очередью тоже закрепилось свое сокращение – FIFO, что значит «First-In, First-Out» – «первым пришел, первым ушел». В отличие от стека, в очередь попадают маловажные события.
Обратите внимание, что элементами очередей и стеков может быть что угодно: события, предметы и даже люди. Рассмотрим два примера: запись в танцевальный кружок и сортировочную горку.
В городе набирали детей в кружок бального танца. Запись в кружок вела преподающая в нём дама. Приходящих мальчишек и девчонок она стремилась объединять в пары при первой возможности с тем, чтобы они сразу приступали к занятиям. Однако на запись дети приходили поодиночке в разное время и в случайном порядке, – то несколько мальчиков подряд, то несколько девочек. Дама не слыхала о системном программировании, а потому прибегла к здравому смыслу. Взяв пару записных книжек, она поступала так.
Если к ней являлось больше мальчиков, дама заносила их в мальчишечью записную книжку, то есть, ставила в очередь. Приняв девочку, она выбирала из этой очереди первого мальчика и составляла пару. Если же являлось больше девочек, то дама ставила их в девчоночью очередь (в другой записной книжке), а с приходом очередного мальчика составляла новую пару. Так, в порядке поступления, составлялись пары мальчиков и девочек.
