Этюды для программистов

Инструментовка. В простейшем варианте эта задача традиционно входит в курсы по Сноболу, но думается, что большинство снобольных реализаций окажутся слишком медленными для практического использования. С другой стороны, язык, не имеющий хотя бы простейших средств для обработки текстов, будет в лучшем случае не слишком удобным. Золотой серединой, пожалуй, был бы язык типа XPL или BLISS. На многих машинах имеются стандартные средства для обработки текстов, например для поиска пробелов, для разбиения цепочек, для сравнения цепочек. Поэтому, для того чтобы извлечь выгоду из этих средств, разумно самые внутренние циклы писать на языке ассемблера.

Длительность исполнения. Одному исполнителю на 4 недели.

Развитие темы. В этой книге можно встретить полужирный шрифт, курсив, греческие буквы, латинские рукописные и другие специальные символы. Все это имелось на выводных устройствах, но, как нетрудно догадаться, ни перфораторы, ни файловая память подобными возможностями не обладают. Для представления таких специальных литер используются специальные соглашения. Пусть, например, слова “et cetera” требуется набрать курсивом. Для этого нужно ввести текст “&i+ et cetera &i−”, и тогда на выводе получится “et cetera”. Тройка литер, начинающаяся значком “&”, называется переключателем шрифта. В данном примере вы видели включение и выключение курсива[10]. Рассматривая подчеркивания, верхние и нижние индексы и т. п. как специальные начертания шрифтов, можно таким образом обеспечить доступ ко всем дополнительным средствам, имеющимся на вашем устройстве вывода. Разумеется, можно включить одновременно несколько переключателей, например чтобы вывести подчеркнутые греческие верхние индексы. (Возможно, вам понадобится также переключатель шрифта для возвратов по тексту вида & × n, где n — цифра от 1 до 9.)

Литература

Керниган, Черри (Kernighan Ё. W., Cherry L. L.). A System for Typesetting Mathematics, CACM, 18, 3, pp. 151–157, 1975.

В этой статье описывается только система для набора математических формул, но система встроена в форматор текстов общего назначения. Сама статья, как, сообщается в журнале САСМ, является фотокопией с результата работы форматора и для публикации повторно не набиралась. Керниган и Черри, между прочим, продают свою систему.

Керниган, Плоджер (Kernighan В. W., Plouger P. J.). Software Tools. Addison-Wesley, Reading MA, 1976.

В книге Кернигана и Плоджера обсуждаются системы программного обеспечения, которые могут оказаться полезными при работе над большим (а пожалуй, и любым) проектом. Каждое такое средство, как и в этих этюдах, сначала обрисовывается в общих чертах, а затем формулируется в виде проекта. Одно из описываемых средств — форматор текстов. Даются также некоторые указания по реализации. Возможно, прежде чем браться за этот этюд, вы захотите сравнить свойства двух форматоров.

* Баяковский Ю. М., Мишакова С. Т. Автоматизированная система подготовки публикаций и документов (АСПИД), ИПМ АН СССР им. М. В. Келдыша. Препринт № 19, 1977.

Система АСПИД написана на Фортране и на машине БЭСМ-6 тратит на подготовку страницы вывода также около 2 с.

5 Победителей судят, или Составление и оценка турнира

Едва ли не каждый из нас в свое время был болельщиком местной, чуть ли не самой сильной команды. Состоявшийся в конце сезона турнир должен был выявить чемпиона города, округа, штата, страны, мира или Вселенной. Но какое невезение — местные герои проиграли будущему победителю уже в первом круге турнира с немедленным выбыванием. Игра оказалась малоинтересной — никто даже не успел размяться. И ведь как обидно: самые настоящие слабаки в итоге занимают место, которое по праву должно принадлежать нашим парням, а болельщиков вместо волнующей борьбы в финале ждет убогое зрелище.

А виноват во всем турнир с немедленным выбыванием. Пусть имеется 2ⁿ команд, n > 0. Тогда в первом круге команда 1 играет с командой 2, команда 3 с командой 4, …, команда 2ⁿ − 1 с командой 2ⁿ. Проигравшие вылетают, а победители выходят в следующий круг.

Рисунок 5.1. Простой турнир с немедленным выбыванием. Окончательное упорядочение, как это определено в тексте, имеет вид 1, 3, 5, 2, 8, 6, 4, 7.