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

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

Головоломка 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 элементов на этой равнине.

Если i = n , то проход таблицы завершен. Мы внаем наилучшую возможную равнину с p повторениями и равнину с r элементами на последнем проходе, Мы берем лучшую из этих двух, и все кончено.

В противном случае нужно продвинуться вперед на один элемент. Либо этот элемент равен непосредственно предшествующему элементу; мы все еще находимся на той же самой равнине, длина которой увеличивается. Либо он отличается от предыдущего; тогда оказывается пройденной равнина длины r, которую при r > p нужно зарегистрировать как наилучшую. С другой стороны, нужно сказать, что новый элемент находится на равнине, которая в данный момент имеет длину 1.

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

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