Книга: Программирование игр и головоломок

6. Комбинаторные задачи

6. Комбинаторные задачи

Головоломка 20. Полное решение.

Поскольку эта задача всюду решена, предложим также и здесь решение: это избавит вас от поисков других решений; и, кроме того, я буду уверен, что вы посмотрели на все существенные места этой задачи. Есть книги, которые… Но это — совсем другая история.

Заметим сначала, что два ферзя не могут находиться на одной строке (горизонтали) и, поскольку нужно поставить 8 ферзей на 8 строк, то на каждой строке есть ферзь. Поэтому я буду говорить «ферзь k» вместо «ферзь, стоящий на строке k».

Точно также, есть только один ферзь в каждом столбце. Но совершенно ясно, что я не могу управлять в одно и то же время размещением и по строкам и по столбцам — собственно, это от меня в задаче и требуется. Я собираюсь поэтому размещать ферзей на последовательных строках, начиная сверху.

Чтобы начать, я помещаю ферзя в первый столбец на первой строке. Тогда мне остается решить меньшую задачу; разместить 7 ферзей на 7 последних строках шахматной доски, учитывая, что ферзь стоит на первом поле первой строки. Я получу тогда все решения с ферзем 1 в столбце 1. Затем я поставлю ферзя 1 в столбец 2 и разрешу задачу с 7 ферзями, и т. д. — 8 раз.

Обобщим. Мы собираемся решить частную, но нужную задачу: полагая, что уже есть ферзи, правильно размещенные на строках от 1 до k ? 1, и зная их положение, найти все возможные решения, размещая подходящим образом ферзей с номерами от k до 8. Обозначим программу, которая это делает, через HR(k)[24]. Стратегия очень проста:

— мы пробегаем все поля на строке k,

— если поле свободно (т. е. не бьется уже поставленными ранее ферзями), то мы ставим на него ферзя k и решаем ту же задачу для k + 1.

При k = 8 задача проще всего. Не может быть более одного свободного столбца. Если он есть, то мы ставим туда последнего ферзя и записываем полученное таким образом решение. Если свободного столбца нет, то нет и решения.

Для задачи HR (k) необходимо знание состояния игры, получающегося после размещения первых k ? 1 ферзей. Это предполагает по крайней мере, что известны столбцы, занятые этими ферзями. Может быть, следовало бы сказать больше. Обозначим символически «занять k, i» операцию, которая констатирует факт, что в столбце i на строке k помещен ферзь.

HR (k =
  ДЛЯ i := 1 ДО 8 ВЫПОЛНЯТЬ
    ЕСЛИ место k, i свободно ТО
      занять k, i
ЕСЛИ k = 8 ТО выписать решение
    ИНАЧЕ HR(к + 1)
    КОНЕЦ_ЕСЛИ
    освободить k, i
  КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ

Операция «освободить k, i» отменяет то, что делает операция «занять k, i». Для решения задачи нужно изложить последовательность инициализации, отмечающую, что ничего не сделано и ни один ферзь в игре не участвует, а затем вызвать HR (1).

Эта процедура рекурсивна, так как она обращается сама к себе. Тщательно изучите ее. Если вы исходите из гипотезы, что HR (k + 1) находит и выводит такие решения, у которых первые k ферзей стоят там, где они поставлены, то у вас не будет никаких затруднений в том, чтобы убедиться, что эта процедура совершенно правильна. Используйте крайние случаи: k = 8 и начальное обращение с k = 1.

Если у вас в наличии нет никакого другого языка, кроме Бейсика, или если вы раб своего языка до такой степени, что не желаете учить что-нибудь, кроме Бейсика, то вам придется писать итеративное решение. Это сложнее.

Будем исходить из наиболее общей ситуации. Пусть на шахматной доске уже размещено k ? 1 ферзей. Обозначим это состояние буквой С (в смысле «самое общее состояние»). Это состояние раскладывается на три подсостояния:

— уже размещено по местам 8 ферзей (k ? 1 = 8): состояние С8;

— на строке с номером k есть допустимое место для ферзя: состояние СОК;

— либо строка с номером k блокирована полностью, либо все возможные поля на ней уже исследованы: СБ.

Запишем кусок программы, который различает эти три случая:

С: ЕСЛИ k = 9 ТО С8
  ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i;
  ЕСЛИ нет таких полей ТО СБ
  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
КОНЕЦ_ЕСЛИ

Рассмотрим теперь каждое из подсостояний.

СОК: есть свободное место в точке k, i. Туда ставим ферзя k и получаем снова самое общее состояние с еще одним размещенным ферзем.

Формально:

СОК: занять k, i; k := k + 1; С

Если строка k блокирована, а также если она полностью исследована, то нужно изменить выбор, который был сделан для ферзя k ? 1, и передвинуть его на свободное место правее (если оно есть). Это возвращение назад относится непосредственно к ферзю k ? 1 и, следовательно, сохраняет только k ? 2 первых ферзей, что вызывает необходимость уменьшить k на 1. Может случиться, что это приведет нас к k = 0, т. е. может случиться, что все места на строке 1 уже исследованы и, следовательно, работа закончена, что мы обозначим как состояние Я, конец программы.

СБ: k := k ? 1;
  ЕСЛИ k = 0 ТО Я
    ИНАЧЕ найти место i ферзя k; освободить k, i;
    найти первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;
    ЕСЛИ нет таких полей ТО СБ
    ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
  КОНЕЦ_ЕСЛИ

Когда 8 ферзей уже размещены, нужно записывать решение. Бесполезно искать другое место для восьмого ферзя, потому что если на восьмой строке и есть свободное место, то только одно. Таким образом, строка 8 оказывается полностью исследованной и нужно снова размещать 7 предыдущих ферзей. А состояние, в котором строка 8 полностью исследована, — это состояние СБ с k = 8.

С8: выписать решение;
  найти место i ферзя 8;
  освободить 8, i;
k := 8; СБ

Остается пустить этот процесс в ход. В начале ни один ферзь в игре не участвует и, следовательно, k ? 1 = 0. Нужна инициализация, которая бы это открыто провозглашала:

ПРОГРАММА: k := 1; инициализировать игру; С

Объединим куски. Мы получим программу, реализующую автомат, как мы уже видели в игре 12. Вы можете рассматривать имена, написанные прописными буквами (С, СБ, СОК, С8, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.

ПРОГРАММА: k := 1; инициализировать игру; С
С: ЕСЛИ k = 9 ТО С8
  ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i;
  ЕСЛИ нет таких полей ТО СБ
  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
КОНЕЦ_ЕСЛИ
СОК: занять k, i; k := k + 1; С
СБ: k := k ? 1;
  ЕСЛИ k = 0 ТО Я
    ИНАЧЕ найти место i ферзя k; освободить k, i;
    ИСКАТЬ первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;
    ЕСЛИ нет таких полей ТО СБ
    ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
  КОНЕЦ_ЕСЛИ
С8: выписать решение;
  найти место i ферзя 8;
  освободить 8, i;
k := 8; СБ

Мы можем улучшить эту программу. Неприятно иметь необходимость находить заново место ферзя в строке, тем более, что знание этого места необходимо дли вывода на экран полученного решения. Заменим i номером c[k] столбца, где расположен ферзь k. Тогда искать место этого ферзя больше не нужно. Именно операция «занять k, i» и будет давать величине c[k] значение i. У нас есть два похожих отрывка в программе:

— в СБ:

искать первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;
ЕСЛИ таких полей нет ТО СБ
ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

— в С:

искать первое свободное поле на строке k и придать значение этого поля величине i;
ЕСЛИ таких полей нет ТО СБ
ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

Второй отрывок идентичен первому, если вместо того, чтобы искать первое свободное поле (что подразумевается как начальный ход), мы потребуем искать первое свободное поле после i, где i придано значение 0. Эту общую последовательность команд мы назовем И (от «искать»). Вот новая программа:

ПРОГРАММА: k := 1; инициализировать игру; С
С: ЕСЛИ k = 9 ТО С8
  ИНАЧЕ c[k] := 0; И
КОНЕЦ_ЕСЛИ
КОНЕЦ_ЕСЛИ
И: искать первое свободное поле на строке k после c[k]
  и придать значение этого поля величине c[k];
  ЕСЛИ таких полей нет ТО СБ
  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
СОК: занять k, c[k]; k := k + 1; С
СБ: k := k ? 1;
  ЕСЛИ k = 0 ТО Я
    ИНАЧЕ освободить k, c[k]
      И
  КОНЕЦ_ЕСЛИ
С8: выписать решение;
k := 8; освободить k, c[k], СБ

Мы можем еще немного выиграть. Значение 9 для k не может быть достигнуто иначе как после размещения ферзя на строке 8 с помощью СОК. Вместо того, чтобы проверять справедливость соотношения к = 9 в С, можно сделать это в СОК. Если нужно разместить восьмого ферзя, то бесполезно требовать «занять k, i» с тем, чтобы сразу после этого освободить указанное поле. Отсюда — новая, еще более простая программа.

ПРОГРАММА: k := 1; инициализировать игру; С
С: c[k] := 0; И
И: искать первое свободное поле на строке k после c[k]
  и придать значение этого поля величине c[k];
  ЕСЛИ таких полей нет ТО СБ
  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
СОК: ЕСЛИ k = 8 ТО записать решение; СБ
  ИНАЧЕ занять k, c[k]; k := k + 1; С
СБ: k := k ? 1;
  ЕСЛИ k = 0 ТО Я
    ИНАЧЕ освободить k, c[k]; И
  КОНЕЦ_ЕСЛИ

Дальше можно выиграть не так уж много, и мы в своих преобразованиях, направленных на улучшение программы, остановимся здесь. Читатель мог бы и удивиться моему способу работать: почему нельзя сразу дать хорошую программу? Потому что, по моему мнению, ее трудно получить сразу. Я мог бы с помощью мелких замечаний представить ее вам без каких-либо промежуточных рассуждений. Читатель был бы восхищен моей сноровкой, но, может быть, заявил бы, что программы такого рода ему самому недоступны, и отказался бы и от этого упражнения, в от остальных упражнений из этого семейства. Если, напротив, читатель находит последнюю программу очевидной, то это потому, что его интуиция намного богаче моей, и он выходит из этой работы ободренный: он еще более ловок, чем автор, браво! И во всех случаях я выигрываю.

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

Если строка блокирована (или после того, как решение выписано), мы поднимаемся строчкой вверх (k := k ? 1 в СБ), освобождая ферзей, пока не окажется возможным передвинуть какого-то ферзя правее (цикл СБ, И, СБ из И). Как только оказывается возможным переместить ферзя правее, он туда перемещается и возобновляется спуск.

Учитывая все это, мы видим, что наша стратегия достаточно проста и выглядит естественной, как только мы к ней привыкаем: ведь привычка — вторая натура, не так ли?

Существенное замечание: я говорю о программе так, как будто она закончена. Но еще ничего завершенного нет: вы никак не можете ввести эту программу в машину, потому что все записано символически. Как вы узнаете, является ли поле свободным? Что это такое — занять поле? Такая ситуация не является исключительной: мы можем обсуждать стратегию программы, совсем не обсуждая представление данных. Две вещи полностью разделены;

— алгоритм или стратегия, которой мы следуем при проведении вычислений;

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

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

— либо, как в рассматриваемом случае, вы приходите к цели. Как только этот первый этап пройден, вы спокойно обсуждаете представление данных;

— либо вы не в состоянии добраться до цели вследствие некоторого влияния структуры данных на стратегию. Такое бывает. Когда вы не можете продвинуться дальше в разработке стратегии, тогда начинайте с выбора представления данных, в котором вам послужит все то, что вы уже сделали к этому времени, и вы учтете то, что вас остановило.

Программирование всегда должно идти нисходящим путем. Сначала — алгоритм или стратегия. Потом — структура данных.

Посмотрим, какие структуры данных возможны в нашей задаче. Первая, наиболее естественная идея: я представляю шахматную доску с помощью квадратной таблицы с 8 строками и 8 столбцами. Я ставлю нули на пустые клетки. Чтобы найти свободное поле на строке, я перебираю поле за полем на строке, пока не нахожу поле с нулем. Это просто. Но как теперь занять поле k, c[k]? Поместив туда значение k. Это тоже просто. Но ферзь, которого нужно разместить, бьет некоторое количество полей, и их уже нельзя будет в дальнейшем занимать. Чтобы это учесть, нужно записать значение к по всем ранее свободным полям, которые теперь бьет этот новый ферзь. Здесь нужен цикл для занятия полей под ферзем на той же вертикали, а затем два других цикла — для каждой из диагоналей, проходящих через это поле (бесполезно занимать поля строки, потому что строка больше рассматриваться не будет). Это проще всего. Что касается освобождения, то нужно пробежать по шахматной доске и заменить там все значения k нулями. Очень долго…

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

Таким образом, нужен вектор с 8 полями, чтобы сказать, свободны ли столбцы. Обозначим этот вектор cm. Тогда cm[i] = 0 будет означать, что в столбце i нет ни одного ферзя. Его не надо путать с c[k], который отвечает на вопрос, в каком столбце стоит ферзь k.

Диагонали характеризуются тем условием, что сумма или разность номеров строки и столбца постоянны. Обозначим через дп диагонали, соответствующие сумме, дм — диагонали, соответствующие разности. В первом приближении диагонали, соответствующие полю k, i, суть дп[k + i] и дм[k ? i].

Но при 1 ? k ? 8, 1 ? i ? 8 сумма меняется от 2 до 16, а разность — от ?7 до 7. Чтобы остаться в промежутке от 1 до 13 (чего некоторые языки просто требуют), нужно вычитать 1 из суммы и прибавлять 8 к разности, Тогда диагонали, проходящие через k, i, суть дп[k + i ? 1] и дм[k ? i + 8].

Операция «искать первое свободное поле…» реализуется маленьким циклом в программе. Вот — на псевдоязыке, используемом в этой книге и близком к Бейсику, LSE и языку Паскаль, — что из всего этого получается:

  ТАБЛИЦА с[8], ст[8], дп[15], дм[15]
    k := 1
  ДЛЯ j := 1 ДО 8 ВЫПОЛНЯТЬ
    ст[j] = 0
  ВЕРНУТЬСЯ
  ДЛЯ j := 1 ДО 15 ВЫПОЛНЯТЬ
    дп[j] := 0; дм := 0
  ВЕРНУТЬСЯ
С c[k] : = 0
И i := c[k] + 1
  ВЫПОЛНЯТЬ
    ЕСЛИ i = 9 ТО КОНЧЕНО
    КОНЕЦ_ЕСЛИ
    ЕСЛИ ст[i] = 0 И дп[k + i ? 1] = 0 И
      дм[k ? i + 8] = 0 ТО КОНЧЕНО
    КОНЕЦ_ЕСЛИ
    i := i + 1
  ВЕРНУТЬСЯ
  ЕСЛИ i = 9 ТО ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ
СОК c[k] := i
  ЕСЛИ k = 8 ТО ВЫВЕСТИ c;
  ПЕРЕЙТИ К СБ КОНЕЦ_ЕСЛИ
  ст[i] := k; дп[k + i ? 1] := k;
  дм[k ? i + 8] := k; k := k + 1
  ПЕРЕЙТИ К С
СБ k := k ? 1
  ЕСЛИ k = 0 ТО ПЕРЕЙТИ К Я КОНЕЦ_ЕСЛИ
  i := c[k]; ст[i] := 0; дп[k + i ? 1] := 0;
  дм[k ? i + 8] := 0
  ПЕРЕЙТИ К И
Я КОНЕЦ_РАБОТЫ

У вас теперь есть все, что только может быть вам нужно для того, чтобы это заработало на вашем компьютере.

Что касается симметрии, то вот указание. Эта программа заставляет первого ферзя пробежать всю первую строку. Но достаточно, чтобы он пробежал половину, а затем дополнить результат по симметрии. Остановить пробег, когда c[1] достигает значения 4, нелегко, но легко начать пробег с цифры 5. Ну, уж теперь-то я сказал вам достаточно…

Я не знаю простого решения для симметрии относительно диагонали. Если вы найдете такое решение, напишите мне…

Головоломка 21.

Я не вижу способа взяться за эту задачу, существенно отличного от предыдущего. Нужно найти нижнюю границу для числа ферзей. На пустой шахматной доске ферзь может блокировать 28 полей. Следовательно, нужно по крайней мере 3 ферзя, чтобы блокировать доску. Их нужно не больше 7: если вы уже пытались вручную поставить 8 ферзей, то вы должны были убедиться, что шахматная доска часто блокируется до того, как мы смогли поставить восьмого ферзя. Точно так же вероятно, что 6 ферзей должно хватить. Поэтому нужно исследовать отрезок от 3 до 6 ферзей.

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

Вы размещаете k ферзей. Вы пробегаете шахматную доску в поисках свободного поля. Если его нет, то у вас есть решение. Если свободное поле есть, то вы ставите туда ферзя и начинаете поиск сначала. Бесполезно пробегать строки, на которых ферзь уже есть, Это соображение ускоряет проверку.

Головоломка 22.

Ничего трудного. Нужно перепробовать все комбинации, Берем какую-нибудь шашку домино в качестве начальной шашки цепочки и пробуем шашки одну за другой. Они вынимаются из хранилища, а затем отыскивается первая шашка, которую можно связать с данной, тем же способом, которым отыскивалось первое свободное поле на следующей строке.

Тщательно выберите ваше представление шашек домино.

Головоломка 23.

И на этот раз программирование достаточно просто. Вы задаете крайние члены последовательности:

a₁ = 0, an = k.

С помощью уже проведенного рассуждения вы можете зафиксировать

a₂ = 1, an_?1 = k ? 2.

Затем вы размещаете следующие члены в интервале (2, k ? 3), например, уплотняя их к началу:

a₃ = 2, a₄ = 3, a₅ = 4…

Вы образуете разности и, если они дают слишком много повторений (вы можете узнать его, не вычисляя всех разностей, что ускоряет тест), вы увеличиваете последний подвижный член a_n?2 и, когда добираетесь до конца, увеличиваете предпоследний подвижный член, затем берете a_n?2 = a_n?3 + 1 и продолжаете дальше.

Для последовательности с 5 членами есть только один подлежащий размещению член, и все идет очень быстро. Но сложность растет с ростом n очень круто. Если при 5 членах есть только один подлежащий размещению член, то с n = 6 их уже два и задача квадратична. Для произвольного n число подлежащих испытанию случаев имеет порядок n^n?4.

Можно, наверное, и еще ускорить. Если даны пак (значение последнего члена), то известно максимальное число возможных повторений, и можно выбрать наилучшие исходные значения. Если есть право на r повторений, то можно брать не более r ? 1 последовательных членов, начиная с a₂, и, если они взяты как исходные значения, то права на повторение больше нет. Тем не менее эта задача расходует огромное количество машинного времени…

Головоломка 24.

В этой задаче я вас полностью предоставляю себе. Принцип все тот же. Но нужно как следует все организовать. Желаю успеха.

Головоломка 25.

Здесь, наоборот, помощь может оказаться далеко не лишней. Эта программа потребовала от меня массу времени. Кроме того, это поучительный случай, который я сохраняю в своих архивах как типичный пример для целого класса задач.

Среди информатиков есть два принципиально разных взгляда на программирование. Есть школа, приверженцы которой сначала проделывают всю математическую работу; они считают, что для того, чтобы написать хорошую программу, нужно сначала доказать некоторое свойство данных, а затем использовать его для получения результата. Сначала сделайте математику, а информатика придет позже. Таким образом, это способствует рассмотрению информатики как ветви математики.

Но есть и другой подход. Напишите сначала программу, пусть даже неэффективную. Затем понаблюдайте за ее поведением или постарайтесь прояснить ее действие. С помощью подходящих преобразований сделайте ее более результативной. Довольно часто я получаю таким образом весьма эффективные результаты, и я убежден, что в этом состоит новый метод создания алгоритмов. Но бывают упорно сопротивляющиеся случаи. Эта головоломка — один из них.

Начну со следующего замечания: речь идет о том, чтобы образовать все возможные перестановки и выбросить все те, которые не удовлетворяют условиям задачи.

Рассмотрим сначала случай 9 девушек. Обозначим их

а, б, в, г, д, е, ж, з, и.

Первая прогулка может быть выбрана произвольно. Возьмем:

а б в
г д е
ж з и

Беря в качестве строк столбцы этой таблицы первой прогулки, получаем вторую прогулку:

а г ж
б д з
в е и

Диагонали приводят к двум оставшимся прогулкам:

а д и   а е з
в г з   б г и
б е ж   в д ж

Все благополучно, Попробуем теперь 15.

Первая прогулка

а б в г д е ж з и к л м н о п

Если вы возьмете в качестве трех первых строк второй прогулки начала столбцов первой прогулки:

а г ж
б д з
в е и

вы не сможете далее организовать 6 оставшихся букв в двух строчках, не повторяя пар. Но вы можете сохранить первые пары в этих трех строках и взять в качестве последних элементов соответственно ж, к, н. Посредством этого приема получаются в двух столбцах по три неиспользованных элемента, которые и можно взять в качестве новых строк. Получается вторая прогулка:

а г ж
б д к
в е н
з л о
и м п

Сейчас мы докажем некоторые свойства искомых прогулок. Но здесь я делаю вам подарок. Мне потребовалось несколько дней, чтобы сообразить все то, что следует ниже. Почему бы вам не предоставить себе несколько дней на размышление? Тогда закройте книгу на этом месте…

Рассмотрим подмножество из семи букв а, б, в, г, д, е, ж. Исходя из этих элементов, можно образовать 7 * 6/2 = 21 пару. В первой прогулке участвует 6 из этих пар:

а — б а — в б — в з — д г — е д — в

Во второй прогулке их пять:

а — г а — ж г — ж б — д в — е

что составляет всего 11 пар. Таким образом, на оставшиеся 5 прогулок остается распределить 10 пар. Но поскольку есть 7 элементов и только 5 строк, то в каждой прогулке будет встречаться не менее двух таких нар. Следовательно, в каждой из оставшихся прогулок встретятся в точности две таких пары. Обозначим через x любую из выделенных букв, а остальные буквы будем обозначать точками. Оставшиеся 5 прогулок имеют вид

x x .
x x .
x . .
x . .
x . .

Но можно еще кое-что уточнить. Рассмотрим только первые 6 букв а, б, в, г, д, е. Они дают 15 пар, из которых 9 реализуются в двух первых прогулках. Таким образом, среди 5 оставшихся прогулок надлежит распределить 6 из них, что означает по одной паре в четырех из них и две в последней. Поэтому получаем:

x x .  x x .  x x .  x x .  x x .
x ж .  x ж .  x ж .  x ж .  x x .
x . .  x . .  x . .  x . .  x . .
x . .  x . .  x . .  x . .  x . .
x . .  x . .  x . .  x . .  ж . .

Заменим ж на к или к и получим тот же результат. Покажите самостоятельно, что в конце концов получаются следующие схемы

x x .  x x .  x x .  x x .  x x .
x ж .  x ж .  x ж .  x ж .  x x .
x к .  x к .  x к .  x к .  x . .
x н .  x н .  x н .  x н .  x . .
x . .  x . .  x . .  x . .  ж к н

Вам остается расставить сначала а, б, в, г, д, е вместо букв x, не возобновляя уже использованных пар, а затем расставить буквы з, и, л, м, о, п вместо точек, соблюдая то же правило. На моем компьютере это отнимает не более 3 минут.

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

Головоломка 26.

Пентамино является другим примером этого утверждения. Общая идея решения проста, если учесть все то, что вы уже сделали. Вы рассматриваете прямоугольную область, которая должна быть покрыта различными кусочками и в начале игры должна быть обозначена вами как пустая,

Вы можете действовать двумя способами: — рассматриваете первое свободное поле и ищете кусок, который можно туда поместить;

— берете первый, еще не использованный кусок и пытаетесь поместить его на игровое поле.

Кусок может быть по-разному ориентирован. Если «I» (прямой брус) может быть размещен в прямоугольнике 3 ? 20 только одним способом (параллельно большей стороне), то «F» (вроде правой нижней фигуры на рис. 31) может быть ориентирован восемью способами. Это зависит в первую очередь от симметрии кусков.

Чтобы не было необходимости определять, какие ориентации допустимы, вы можете задать — в качестве программных констант — все эти возможные положения каждого куска.

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

Тогда я стал пытаться избежать большого числа испытания, исходя аз замечания, сделанного при постановке задачи: кусок не должен определять в игре «островок» с площадью, не кратной пяти. Но определение островков нетривиально…

Я действую следующим образом. Я отыскиваю заполнение прямоугольника; параллельно меньшей стороне, Рисунок 39 показывает возможную ситуацию в ходе выполнения этого плана.

Рассмотрим тогда конфигурацию, окружающую крайнее левое из свободных полей. Обозначив через «x» занятые поля и полагая свободные поля точками, мы получим не более 7 возможных случаев (если вы привыкли к двоичной нумерации, то это покажется вам очевидным): см. рис. 40.

В крайней левой ситуации будем искать способ занять свободное поле на верхней строке. Но ни один из кусков ни в какой из их ориентации не подходит. Вы не можете использовать ни крест, ни «F», ни «Z». Кусок «С» можно использовать только с большей стороной по вертикали…

Я закрепил за каждой конфигурацией список допустимых в ней кусков, и если такие куски есть, подробный список их возможных ориентаций. Это существенно уменьшает число попыток. Еще оказывается, что время от времени появляются острова недопустимой площади, но они существуют только очень короткое время. Я узнал это, поскольку я выводил на экран состояние игры всякий раз, когда в игру входил новый кусок, Этот способ действия имеет много преимуществ:

— очень неудобно иметь программу, которая работает несколько десятков минут (порядка 45 на моем микрокомпьютере), а мы ничего не знаем о том, что в ней происходит, Это неудобно как собственно для работы, так в для того, чтобы сразу же задавать вопросы. А если, хотя бы это и было ошибкой набора, вдруг найдется бесконечный цикл…

— этот вывод позволяет видеть работу компьютера. Видно, как один за другим исследуются куски, как игровое поле более или менее наполняется (иногда вплоть до одиннадцати кусков. Если вы пытались решить эту головоломку вручную, отметили ли вы, какое впечатление производит нехватка одного куска? Однако это просто: если остается островок площади 5, то он обязательно имеет форму одного из игровых кусков…). Затем она почти полностью опустошается, и возобновляется заполнение…

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

Для вывода на экран я не нашел хорошего рисунка, потому что у меня нет ни графического, ни полуграфического экрана — только алфавитно-цифровой. Каждому куску я сопоставил букву и вывожу куски на экран в виде подходящим образом расположенных пяти букв. Такой вывод показан на рис. 41.

Я представляю игру внутренним образом в виде цепочки символов по двум причинам:

— используемый мною язык (LSE) в используемой мною версии является одним из наиболее эффективных языков для работы с цепочками символов. Это почти также быстро, как если использовать таблицы. Я могу очень быстро найти первое свободное место, я могу очень быстро узнать, свободно ли поле (является ли символ на этом месте в цепочке точкой?);

— вывод мгновенный: я вывожу на экран три подцепочки на трех последовательных строках.

Остается еще установить немало деталей, касающихся представления кусков. Но вы же не ждете, что я за вас сразу и программу напишу?

Головоломка 27.

А эта программа простая. Вам нужно образовать выражение вида

a1?a2?a3?…?ap,

где операция, обозначенная ?, означает либо сложение, либо вычитание. Есть p ? 1 знак, каждый из которых может принимать два значения. Это дает 2^p?1 возможных значений. Каким бы ни был способ, которым вы их перебираете, вам нужно перепробовать их все (по крайней мере в случае, когда число s таково, что решения нет).

Два знака «+» и «?», так что снова двоичная система. Вы можете воспользоваться этим замечанием при составлении программы. Меняем целое число от нуля до 2^p?1. Для каждого из значений рассматриваем его двоичное представление. Ставим в выражении «+» на тех местах, где стоят нули, и «?» на местах, где стоят единицы. Но в этом таится опасность побудить некоторых написать программу на языке ассемблера, что было бы ошибкой (по моему мнению. Вы тогда сплутовали бы. Есть хорошие алгоритмы на развитом языке. Не меняйте условий задачи, выписывая алгоритм, который оказался бы необъяснимым).

Вы можете также — и это, конечно, более эффективный способ — поставить знаки «+» в начале выражения и исчерпать все комбинации с тем, что осталось, затем заменить последний знак «+» на «?» и т. д, С четырьмя числами вы получите последовательно:

+++

++?

+?+

+??

?++

?+?

??+

???

Состояние знаков хранится в таблице или в цепочке.

Заметьте, что рассматриваемая задача имеет простое рекурсивное решение. Достаточно испробовать две комбинации:

a₁ + — любая комбинация, которая может быть составлена из p ? 1 оставшихся шашек,

a₁ ? — любая комбинация, которую можно составить из оставшихся шашек.

Должно получиться:

s = a₁ + — комбинация из n ? 1 чисел или

s = a₁ ? — комбинация из n ? 1 чисел.

Заметим, что разность нужно брать по абсолютному значению.

Таким образом, остается искать способ представления s + a₁ или s ? a₁ помощью n ? 1 оставшихся шашек. Такую процедуру легко написать. Таблица чисел может быть глобальной величиной. Чтобы сохранять только n ? 1 чисел, кроме первого, достаточно сказать, что таблица рассматривается, начиная с индекса 2. Следовательно, нужна процедура, в которой в качестве параметров берутся:

индекс, начиная с которого должны рассматриваться числа,

сумма, которую нужно найти.

Итеративные формы программы, которые вы сможете написать, суть немедленные переводы на итеративный язык этой рекурсивной формы.

Головоломка 28.

Решение, набросок которого я привожу здесь, принадлежит не мне. Я нашел его вышедшим из-под пера Николь Брео Поликен и Оливера Герца в журнале «Персональный компьютер» (L?ordinateur individuel) за март 1983 г.

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

Я переписал это решение практически без изменений на LSE83 (намного более структурированная форма LSE, соединяющая преимущества структурирования языка Паскаль с возможностями манипуляций с цепочками символов, имеющихся в LSE, и, сверх того, облегчением программирования сверху вниз), и результат немедленно оказался удовлетворительным. Все это служит прославлению авторов. Как же могло тогда случиться, что пояснения, которые авторы дают к своей программе, до такой степени недоступны пониманию, что мне потребовался большой труд, чтобы достичь понимания их метода? Там, действительно, есть две или три «хитрости», которые гораздо больше заслуживали комментария, чем тот факт, что из-за рекурсии результаты записываются в порядке, обратном порядку их получения…

Сохраним предположения работы этих авторов, приведенные в условиях задачи. Зачем от них отказываться? Например, такая комбинация, как

n = p₁ * p₂ + p₃ * p₄ ? p₅/p₆

не сводится ни к одной из предложенных форм.

Программа, написанная авторами, рекурсивна, но ее читателю доставляют затруднения две особенности ее написания:

— как я уже указывал, некоторые переменные, являющиеся локальными в одной процедуре, глобальны в другой… Конечно, это может быть обнаружено при внимательном чтении текста, но это и требует внимания;

— некоторые процедуры мультиформны и дают совершенно различные результаты в зависимости от значений формальных параметров.

Вернемся к задаче в той форме, в какой она была поставлена. Что нужно делать?

Сначала пройдем по таблице шашек от 1 до 6. Для каждой шашки p_i посмотрим, делится ли n на p_i. Если да, то нужно решать меньшую задачу: образовать число n/p[i] с помощью пяти шашек, получаемых удалением шашки i из набора. Если n не делится ни на одну из шашек или если поиск шашки, на которую делится n, потерпел неудачу, то для каждой шашки i ищем решение задачи: образовать n + p[i] или n ? p[i] с помощью 5 шашек, получаемых изъятием шашки i из набора. Но здесь мы довольствуемся решением, которое должно иметь вид произведения одной из шашек на комбинацию четырех остальных.

Цитируемые здесь авторы решают эту задачу изъятия некоторых шашек из набора переписыванием начальной таблицы шашек в другую, перепрыгивая через шашки, подлежащие изъятию,

Я действую по-другому. Я помещаю 6 шашек в таблицу из 6 чисел, скажем a. В начале они упорядочены и расположены в неубывающем порядке. Чтобы изъять шашку из этого множества, мне достаточно переставить ее с шестой шашкой, а затем работать с первыми 5 элементами таблицы a. Таким образом, я создаю две процедуры: процедуру

П (p, x),

которая ищет способ представить x с помощью p первых значений таблицы a, причем это решение должно иметь вид произведения одной из шашек на некоторую комбинацию остальных (П поставлено для решения в виде Произведения);

процедуру

О (p, x),

которая ищет решения задачи о формировании x из p первых шашек, в котором результат имеет какую-нибудь из форм, предложенных в формулировке задачи (О — от Общее),

Программа довольствуется чтением 6 шашек (в порядке возрастания) и числа n, которое нужно найти, а затем вызывает О (6, n).

Вся задача состоит в том, чтобы поддерживать часть таблицы от 1 до p в неубывающем порядке. Это нетрудно. Вот схематическое описание процедуры П. В нем t является глобальной булевой переменной, которой присвоено начальное значение ЛОЖЬ.

П (p, x)
ЕСЛИ p < 3 ТО упрощенная форма;
КОНЧЕНО КОНЕЦ_ЕСЛИ
i := p
ВЫПОЛНЯТЬ
  ЕСЛИ x = a[p] ТО ИСТИНА; КОНЧЕНО
  КОНЕЦ_ЕСЛИ
up := x/a[p]; u = целая_часть(up)
  ЕСЛИ u = up ТО О (p ? 1, u);
    ЕСЛИ t ТО ВЫВЕСТИ u, '*', а [р], '=', x
    КОНЧЕНО КОНЕЦ_ЕСЛИ
  КОНЕЦ_ЕСЛИ
  i := i ? 1; ЕСЛИ i = 0 ТО
  КОНЧЕНО КОНЕЦ_ЕСЛИ
  переставить (i, p)
ВЕРНУТЬСЯ

Вы покажете, что часть от 1 до р ? 1 остается расположенной в неубывающем порядке. Но при выходе из цикла в p стоит элемент, который меньше всех остальных. Следовательно, нужно восстановить исходный порядок в части от 1 до p, если t не принимает значения ИСТИНА (в противном случае все кончено). Это вы легко изобретете.

Процедура О вдохновляется той же идеей, но есть два цикла:

— один, приводящий в p все элементы один за другим;

— другой, который приводит в p ? 1 элементы, расположенные ниже того, который попал в p.

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

Наконец, нужно заметить, что эта процедура прекрасно подходит для итеративного переписывания, Создаем вектор x, дающий искомое число для каждого p. Как и выше, индексы i и j процедур Па О связаны с p. Наконец, переменную p сделали глобальной. Мне кажется достаточно очевидным, что итеративная процедура не пойдет намного быстрее рекурсивной процедуры: придется делать много проверок, которые выполнялись автоматически на уровне машинного языка, исполняющей системой. Но это и есть способ выйти из положения в случае, если, к несчастью, у нас нет рекурсивности.

Если у вас есть предубеждения против рекурсии, то сейчас подходящий момент избавиться от них. И бросьте думать, что рекурсия всегда дорого обходится. Она всегда сокращает время программирования. Неверно, что она всегда приводит к более медленному вычислению (эта головоломка и есть пример). Я соглашусь с вами, что она всегда занимает немного больше места…

Эта процедура, действуя на 6 шашек

100 75 50 25 10 10,

быстро находит число 370, но терпит неудачу для 369.

Оглавление книги