Программирование игр и головоломок - [52]
У вас есть также некоторое число таких p>i, что диагональ, выходящая из p>i − 1, 1, не пересекает никакого отрезка нулей перед осью q, что дает g>i = (p>i − 1) : 2.
Исходя отсюда, следующие числа p определяются диагоналями, которые перерезают вертикальный отрезок, выходящий из p>i так, что p − p>i ≤ g>i = (p>i − 1) : 2. Тогда можно восстановить первоначальную последовательность, несущую нули, вплоть до (p>i − 1) : 2.
Теперь вы легко сможете доказать, что интересующая нас последовательность p>i есть последовательность чисел Фибоначчи.
Составьте программу, перечисляющую p>i, g>i.
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, и передвинуть его на свободное место правее (если оно есть). Это возвращение назад относится непосредственно к ферзю
