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

Арсак Жак

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

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

Очевидно, что мы очень многого не знаем. Следовательно, нужно тщательно прочесть условие и выделить все данные. Невозможно, чтобы на каждый вопрос решительно все ученики ответили неправильно, потому что если бы это случилось, то они все получили бы 0. Следовательно, на каждый из вопросов есть правильный ответ, который либо является одним из чисел, входящих в ответы учеников, либо другим числом (и тогда более или менее все равно каким).

Таким образом, правильный ответ на первый вопрос может быть одним из чисел

8 12 16 20 и другим числом, скажем 24,

чтобы ответы образовывали арифметическую прогрессию с разностью 4. Сделаем то же самое для других вопросов. Таким образом, вы получите, например:

R1: 8 12 16 20 24

R2: 12 14 16 18

RЗ: 10 12 14

R4: 16 18 20 22 24

Исследуем

все полученные из оценок четверки чисел, отводя по строчке для каждой из них. Они образуют 5*4*3*5 = 300 строк. Для каждой из них ваша программа смотрит, сколько учеников получило 0, и запоминает только те четверки чисел, для которых один и только один ученик получил 0 (это дано в условии). Заметьте к тому же, что вам сообщено, что ответом на один из вопросов должна быть площадь поверхности куба с целым ребром, следовательно, число вида 6n², возможные значения которого 6, 24… Ни один из ответов не имеет вида 6n² с целым n. Следовательно, мы должны получить, что в выделенных четверках есть одна или несколько четверок, у которых хотя бы одна компонента имеет значение, не предложенное ни одним из учеников. Ваша программа легко их найдет (такой набор в точности один). На этом основании мы узнаем правильность всех ответов на вопросы, остальное просто.

При всем том, это — головоломка для начинающих…

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

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

Я совершил ошибку, пойдя по этому пути. Я сказал себе: назовем S(i, j) сумму элементов вектора с номерами от i до j:

S(i, j) = a_i + a_i+1 + … + a_{j– 1} + a_j.

Если для некоторой пары i, j эта сумма максимальна, то отсюда следует

S(i, j) > S(i + 1, j)

и, следовательно, a_i > 0. Точно так же a_i + a_i+1 > 0.

Если обобщить любое «начало» (левая часть) S(i, j) положительно, и точно так же любой «конец» положителен. Можно продолжать:

a_{i– 1} отрицателен…

И я таким образом не получил ничего. Это не означает утверждения, что на этом пути нельзя найти решения. Это я его не нашел.

Как я уже говорил, вы можете обратиться к математике за помощью в решении вашей задачи по информатике [28] . Но у информатики есть и свой собственный творческий дух. Почему бы ему не довериться? Эта задача сбивает вас с толку по причине ограничений на сложность алгоритма. Забудем их. Если вам сказано, что нужно решить задачу, и вам предоставлена свобода вплоть до максимальной сложности, что вы будете делать? Вы составите таблицу S (i, j) для i = 1, …, n и j = i, …, n. В этой таблице вы возьмете максимальный элемент.

28

В математике для решения этой задачи есть полезная формула Ньютона-Лейбница:

где F —функция,

определяемая условием F(x) = f(x), x [p, q]. Впрочем, все эти интегралы нам не понадобятся, так как у этой формулы есть гораздо более простой аналог для сумм: a_i + a_i+1 + … + a_j = b_j– b_{i– 1}, где последовательность {b} определяется условием, что b_k– b_{k– 1} = а_k для любого k от 1 до n. Последовательность {b} легко построить: b₀ = 0, b_k+1 = b_k + a_k+1. Для последовательности {b} задача ставится так: найти такие i < j, что разность b_j– b_i максимальна. С этой задачей уже легче справиться. — Примеч. ред.

Чтобы помочь вам, я предлагаю вам рассмотреть следующий вектор:

3 4 -8 2 -3 7 5 -6 1

Образуйте треугольную таблицу чисел S (i, j) и запишите ее. Посмотрите, как каждая строчка образуется из предыдущей. Вы увидите, что только три строчки могут содержать максимальное S и, кроме того, не во всей их полной длине. В этом примере максимум нужно искать среди

(1, 1 : 3), (4, 4 : 5), (6, 6 : 9).

Следовательно, есть в точности n значений S, которые нужно рассматривать. Таким способом вы и получаете алгоритм, линейный по n.

Закончить предоставляю вам.

Часть III. И если вы все еще не нашли решения

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

1. Случайные числа

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

Первая стратегия. Нужно сравнить u_2i и u_i. Они равны, если 2i = i + kp для целого k, следовательно, если i делится на p. Кроме того, i должно превосходить r. Следовательно, нужно искать наименьшее кратное p, большее или равное r.

Положим v_i = u_2i. Тогда

v_i+1 = u_2i+2 = f(f(u_2i)) = f(f(v_i)).

Если вы начинаете u с u₁ = a, то вы начинаете v с v₁ = f(а).