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

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

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

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

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

Есть карточный пасьянс, который более иди менее похож на эту задачу. Выберем из вектора его первый элемент и отложим его в сторону на запасное поле, Мы можем поместить на его место элемент m + 1, который и должен перейти на поле 1. Теперь поле m + 1 свободно. Туда можно перенести элемент, который должен его заполнить. Возьмем конкретный пример: n = 10 и m = 4. Элементы верхней части спускаются на 4 поля, а те, которые находятся в нижней части, поднимаются на 6 полей. Вот последовательные состояния вектора. Я не представляю здесь запасное поле, которое содержит элемент 1. Я помещаю в эти поля именно номера элементов в исходной конфигурации:

исходное положение:

1 2 3 4 5 6 7 8 9 10

2 3 4 5 6 7 8 9 10

5 2 3 4 6 7 8 9 10

5 2 3 4 9 6 7 8 10

5 2 4 9 6 7 8 3 10

5 2 7 4 9 6 8 3 10

А теперь именно элемент 1 должен прийти на свободное поле, и этот цикл останавливается. Мы убеждаемся, что не все элементы перенесены. Все числа на нечетных местах уже находятся там, где должны находиться, а числа на четных местах не стронуты с мест. Но можно начать новый цикл той же длины, поместив 2 на запасное поле, — это завершит работу.

Предлагая эту задачу профессиональным программистам, я очень редко получал такое решение, потому что им не удавалось выяснить, что мы действительно перемещаем таким образом все элементы (в этом можно убедиться, подсчитывая число движений) и нет ли опасности дважды переместить один и тот же элемент, так что конечное состояние оказалось бы неправильным [25] При чтении этого абзаца вспоминается шутка Маяковского. После одного из своих выступлений он получил из зала записку: «Мы с товарищем слушали ваши стихи и ничего не поняли». Маяковский ответил: «Нужно иметь умных товарищей». — Примеч. ред. .

Чтобы навести себя на правильный путь, заметьте, что если верхние элементы спускаются на m полей, то нижние элементы поднимаются на n − m полей.

Вы не видите? Есть n полей. Вы работаете в арифметике по модулю n . По модулю n все элементы спускаются на m полей. На этот раз вы должны найти решение, учитывая влияние на ход решения наибольшего общего делителя m и n … [26] Если разрешить перемещать каждый элемент вектора не один раз, а два, то можно найти изящное и простое решение, в котором и речи нет ни о каких общих делителях. Представим себе элементы вектора расположенными по окружности на равных расстояниях друг от друга. Нам нужно повернуть эти векторы на угол. Используйте тот факт, что всякий поворот окружности можно получить, выполнив подряд две осевые симметрии. — Примеч. ред.

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

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

Следовательно, Предположим, что мы прошли таблицу до номера i включительно. Пусть в пройденной части мы нашли, что элемент со значением x повторялся p раз, и пусть это — максимальное число повторений.

Но нужно еще более уточнить ситуацию в точке остановки. У нас есть две возможности.

— Первая идея: мы останавливаемся в конце равнинного участка.

Если i = n , то мы прошли всю таблицу, узнали наилучший равнинный участок, и все закончено. В противном случае мы пробегаем следующую равнину и измеряем ее длину r. Если r ≤ p , то наилучшая равнина остается неизменной, а в противном случае именно последняя равнина и регистрируется заново как наилучшая, и мы возобновляем движение по таблице. Это просто, и это легко программировать. Запишите это решение, чтобы иметь возможность сравнить его с другими решениями.

— Вторая идея: мы останавливаемся в произвольной точке i . Мы оказываемся на некоторой равнине и уже нашли r элементов на этой равнине.