Программирование игр и головоломок
Шрифт:
Но есть и другой подход. Напишите сначала программу, пусть даже неэффективную. Затем понаблюдайте за ее поведением или постарайтесь прояснить ее действие. С помощью подходящих преобразований сделайте ее более результативной. Довольно часто я получаю таким образом весьма эффективные результаты, и я убежден, что в этом состоит новый метод создания алгоритмов. Но бывают упорно сопротивляющиеся случаи. Эта головоломка — один из них.
Начну со следующего замечания: речь идет о том, чтобы образовать все возможные перестановки и выбросить все те, которые не удовлетворяют условиям задачи.
Рассмотрим сначала случай 9 девушек. Обозначим их
а, б, в, г, д, е, ж, з, и.
Первая
Беря в качестве строк столбцы этой таблицы первой прогулки, получаем вторую прогулку:
Диагонали приводят к двум оставшимся прогулкам:
Все благополучно, Попробуем теперь 15.
Первая прогулка
а б в г д е ж з и к л м н о п
Если вы возьмете в качестве трех первых строк второй прогулки начала столбцов первой прогулки:
вы не сможете далее организовать 6 оставшихся букв в двух строчках, не повторяя пар. Но вы можете сохранить первые пары в этих трех строках и взять в качестве последних элементов соответственно ж, к, н. Посредством этого приема получаются в двух столбцах по три неиспользованных элемента, которые и можно взять в качестве новых строк. Получается вторая прогулка:
Сейчас мы докажем некоторые свойства искомых прогулок. Но здесь я делаю вам подарок. Мне потребовалось несколько дней, чтобы сообразить все то, что следует ниже. Почему бы вам не предоставить себе несколько дней на размышление? Тогда закройте книгу на этом месте…
Рассмотрим подмножество из семи букв а, б, в, г, д, е, ж. Исходя из этих элементов, можно образовать 7 * 6/2 = 21 пару. В первой прогулке участвует 6 из этих пар:
а — б а — в
Во второй прогулке их пять:
а — г а — ж г — ж б — д в — е
что составляет всего 11 пар. Таким образом, на оставшиеся 5 прогулок остается распределить 10 пар. Но поскольку есть 7 элементов и только 5 строк, то в каждой прогулке будет встречаться не менее двух таких нар. Следовательно, в каждой из оставшихся прогулок встретятся в точности две таких пары. Обозначим через x любую из выделенных букв, а остальные буквы будем обозначать точками. Оставшиеся 5 прогулок имеют вид
Но можно еще кое-что уточнить. Рассмотрим только первые 6 букв а, б, в, г, д, е. Они дают 15 пар, из которых 9 реализуются в двух первых прогулках. Таким образом, среди 5 оставшихся прогулок надлежит распределить 6 из них, что означает по одной паре в четырех из них и две в последней. Поэтому получаем:
Заменим ж на к или к и получим тот же результат. Покажите самостоятельно, что в конце концов получаются следующие схемы