Жак Арсак - Программирование игр и головоломок

Головоломка 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 . .