Этюды для программистов - [13]
Длительность исполнения. Одному исполнителю на 4 недели.
Развитие темы. В этой книге можно встретить полужирный шрифт, курсив, греческие буквы, латинские рукописные и другие специальные символы. Все это имелось на выводных устройствах, но, как нетрудно догадаться, ни перфораторы, ни файловая память подобными возможностями не обладают. Для представления таких специальных литер используются специальные соглашения. Пусть, например, слова “et cetera” требуется набрать курсивом. Для этого нужно ввести текст “&i+ et cetera &i−”, и тогда на выводе получится “et cetera”. Тройка литер, начинающаяся значком “&”, называется переключателем шрифта. В данном примере вы видели включение и выключение курсива[10]. Рассматривая подчеркивания, верхние и нижние индексы и т. п. как специальные начертания шрифтов, можно таким образом обеспечить доступ ко всем дополнительным средствам, имеющимся на вашем устройстве вывода. Разумеется, можно включить одновременно несколько переключателей, например чтобы вывести подчеркнутые греческие верхние индексы. (Возможно, вам понадобится также переключатель шрифта для возвратов по тексту вида & × n, где n — цифра от 1 до 9.)
Керниган, Черри (Kernighan B. 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 команд, n > 0. Тогда в первом круге команда 1 играет с командой 2, команда 3 с командой 4, …, команда 2>n − 1 с командой 2>n. Проигравшие вылетают, а победители выходят в следующий круг.
Рисунок 5.1. Простой турнир с немедленным выбыванием. Окончательное упорядочение, как это определено в тексте, имеет вид 1, 3, 5, 2, 8, 6, 4, 7.
На рис. 5.1 изображен турнир восьми команд. Если предположить, что более сильная команда всегда выигрывает (т. е. что не бывает срывов), лучшая команда, очевидно, завоюет первое место. Однако второй участник финальной игры может занимать в общей табели о рангах лишь место 2>n−1 + 1 при условии, что все более сильные команды оказались в одной группе с победителем. Победитель по мере своего продвижения выведет из розыгрыша хорошие команды, и слабой команде достанутся совсем никудышные соперники. Избежать подобной ситуации можно несколькими способами. Во-первых, команды (в дальнейшем будем называть их соперниками) можно рассеять, чтобы сильные соперники (оценка дается по итогам предыдущих выступлений) разместились по всей турнирной сетке. Например, самый сильный соперник попадает в позицию 1, второй по силе — в 2>n−1 + 1, третий — в 2>n−1 + 2>n−2 + 1, четвертый — в 2>n−2 + 1 и т. д. Если предварительная оценка была достаточно точной, сильные соперники не выбьют друг друга в первых кругах. Во-вторых, можно устроить турнир с отложенным выбыванием, когда выбывают после двух поражений. Но на самом деле идеальным решением (хорошо бы еще и практичным!) был бы круговой турнир, в котором все соперники играют друг с другом ровно один раз. В предположении отсутствия срывов сильнейший соперник выиграет 2>n − 1 встреч и проиграет 0, второй по силе соответственно 2>n — 2 и 1 (уступит лишь сильнейшему), …, а самый слабый — 0 и 2>n − 1 (проиграет всем). Трудность в том, что в круговом турнире нужно провести 2>n−1(2>n − 1) встреч, в то время как в турнире с немедленным выбыванием лишь 2
