Стрейчи (Strachey С). A General Purpose Macrogenerator. Comput. J. 8, 3, pp. 225—241, 1966.
В статье Муэрса Трак описывается с точки зрения его использования. Изложение проблем во многом повторяет предыдущую статью, но во встроенные функции внесены некоторые очевидные усовершенствования. Стрейчи в своей статье описывает очень похожий язык, в котором вместо встроенных функций имеются более мощные, чем в Траке, средства определения функций, и приводит листинг модельного процессора. Две эти статьи были написаны независимо и представляют собой яркий образец проявления исторической необходимости.
Вегнер (Wegner P.). Programming Languages, Information Structures, and Machine Organization. McGraw-Hill, New York, NY, 1978.
И Браун, и Вегнер с позиций общей информатики обсуждают Трак наряду с другими макропроцессорами.
РЕШЕНИЯ
Ниже в качестве решений представлены законченные программы, однако это далеко не все, что должны сделать студенты. На примере конкретных задач мы обсуждаем искусство программирования, в частности некоторые полезные нюансы, о которых умалчивают многие руководства. Студентам необходимо представить больше внешней документации, больше выдач, больше подтверждений правильности программ. Заметим также, что мы не навязываем другим выбранные нами языки.
29. Красьте с нами,
или...
ПОЛНОЕ РЕШЕНИЕ ЗАДАЧИ
В данной главе в полном виде приводится программа для задачи о раскраске карты (см. гл. 3). Читатели, которым довелось испытать это на собственной шкуре, знают как трудно описывать программу, излагая алгоритм прозрачно и просто. Когда решение головоломки рассказано, обычной реакцией бывает: «Как я не догадался!» вместо: «Как здорово!» Ну а программа — это, конечно, тоже решение головоломки. Из описаний всегда устраняют дух исследования, историю неудавшихся подходов и отступлений, упоминание о глупых ошибках, сбивавших с правильного пути. Если бы мы попытались полностью изложить процесс разработки программы, вы бы не знали, плакать вам или смеяться над тупостью автора. Так что лучше пойдем уже проторенной дорогой от задачи к решению, лишь изредка поглядывая по сторонам. [61]
По условию задачи требуется раскрасить карту или неориентированный граф в минимальное число цветов так, чтобы никакие два соседних региона (никакие две смежные вершины) не были одного цвета. Хотя в данный момент не требуется точно специфицировать формат исходной и выводимой информации, а также внутреннее представление данных, можно сообразить, какие свойства графа будут существенны для любой программы. Очевидно, нужно знать число вершин графа, уметь регулярным образом обращаться к вершинам, уметь раскрашивать вершины и узнавать их цвет, определять, являются ли две вершины смежными, и, наконец, нужно уметь порождать много различных цветов. Проще всего удовлетворить перечисленным требованиям, обозначив вершины натуральными числами 1, 2, ..., n, где n — общее количество вершин. Аналогично и цвета обозначим натуральными числами (ясно, что при этом в нашем распоряжении окажется много цветов). Вопрос о конкретном способе определения смежности вершин целесообразно отложить.
Раскрашивать можно двумя способами: либо предположить, что каждая вершина уже раскрашена в свой цвет и попытаться избавиться от нескольких цветов, либо предположить, что ни одна вершина еще не раскрашена, и пытаться добавлять как можно меньше цветов. Однако на любом пути мы сталкиваемся с неприятным теоретическим результатом (или с отсутствием оного): никто не знает, как раскрасить карту, не перебрав для худшего случая все возможные раскраски с минимальным числом цветов. Большинство специалистов считает, что нет более быстрого метода раскрашивания карты, чем перебор всех вариантов. Иными словами, какой бы умной ни была ваша программа и как бы быстро она ни работала в среднем, найдутся карты с n вершинами, требующие к цветов, на раскраску которых программа затратит порядка kn единиц времени. Возможно, кому-нибудь посчастливится найти алгоритм, и для худшего случая оказывавшийся не столь расточительным, но теоретики считают это маловероятным. Так что давайте займемся простой быстрой программой, а не суперсложной, которая вряд ли будет лучше.[62]
Предлагаемое решение основано на наблюдении, что если некоторый подграф нельзя раскрасить в k цветов, то и весь граф, очевидно, тоже нельзя раскрасить в к цветов. На каждом шаге нашего алгоритма мы пытаемся добавить к уже раскрашенному подграфу еще одну вершину. Если сделать это не удастся, текущий раскрашенный подграф перекрашивается всеми возможными способами с использованием тех же цветов. Если новую вершину добавить все же нельзя, число цветов увеличивается на единицу» поскольку найден подграф, не раскрашиваемый выделенными цветами. В описании алгоритма предполагается, что есть вектор цвет, содержащий цвета, приписанные каждой вершине. Логическая функция связь позволяет узнать, связана ли вершина i с вершиной j.
61
Для усиления аналогии между трудом писателя и программиста отметим, что данная глава переписывалась не раз и не два
62
Данная программа иллюстрирует важность теоретической информатики для программистов-практиков. Многие другие распространенные комбинаторные задачи, среди которых наиболее известна задача о коммивояжере, в наихудшем случае требуют для своего решения такой же крайней расточительности, как и раскрашивание карты. Но довольно часто небольшое изменение условия делает возможным очень эффективное решение. Программисту не нужно знать все задачи и их решения, однако он должен узнавать трудные задачи и обращаться за решениями к литературе или специалистам. Между прочим, если не требуется оптимальное, минимальное, максимальное или точное решение, целесообразно испробовать имеющиеся для многих задач эвристики, позволяющие быстро получить хорошие приближения