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

и, следовательно, 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. В этой таблице вы возьмете максимальный элемент.

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

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(а).

Таким образом, получаем начало программы:

u := a; v := f(а)

ПОКА u ≠ v ВЫПОЛНЯТЬ

  u := f(u); v := f(f(v))

ВЕРНУТЬСЯ

Теперь вы получили два равных элемента. Чтобы получить период, нужно пройти интервал между полученными числами — например, начиная с u — считая число элементов:

p := 1; w := f(u)

ПОКА w ≠ u ВЫПОЛНЯТЬ

  w := f(w); p := p + 1

ВЕРНУТЬСЯ

Мне пришлось рассказать вам все…

Вторая стратегия. Начните с d = 1 и h = 1. Если вы не находите периодичности в интервале от d + 1 до d + h (сравнивая u на этом интервале со значением u на элементе d, сохраняемым в некоторой переменной, например, x), возьмите значение u в d + h в качестве нового значения x, d + h в качестве нового d, и удвойте k.

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

Игра 4.

Если вы представляете игровое ноле прямоугольной таблицей, то перемещение обозначается изменением координат точки: добавлением или вычитанием чисел 1 или 2. Я разместил эти добавляемые количества (целые числа со знаком) в два вектора DX, DY из 8 элементов. Одно направление перемещения задается номером поля в этой таблице, следовательно, целым числом от 1 до 8.

2. Игры с числами

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

Остановитесь, когда вы получите 5 в качестве цифры единиц с нулем «в уме».

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

Представленный здесь алгоритм эквивалентен алгоритму, который можно найти в старых книгах по арифметике, и который действует на целые числа, разбитые на куски но 2 цифры в каждом куске. Вы можете либо разыскать доказательство в этих книгах, либо посмотреть в моей книге «Основы программирования», как можно доказать, что программа, реализующая этот алгоритм, действительно вычисляет квадратный корень. Но это рассуждение слишком сложно, чтобы воспроизводить его здесь.

Лично я работаю по основанию 10. Я представляю числа цепочками цифр. Присоединить 1 справа легко: это просто конкатенация. Сдвинуть вправо легко: используется индекс, сообщающий, начиная с какой позиции нужно урезать. Именно этот индекс и изменяется. Складывать с 2 легко, так как может быть не более одного переноса. Единственная тонкая операция — вычитание, Не проводите сравнения перед вычитанием: оно стоит так же дорого, как и само вычитание. Сделайте копию той части, которая должна была бы быть изменена при вычитании, и если вы обнаружите, что вы не можете осуществить вычитание, — возьмите сохраненное значение.

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