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

1. Число делится на 2. После однократного деления на 2 оно не будет иметь других делителей нуля, кроме 2, 3 и 5. Следовательно, это число — из последовательности. Так как 50 : 2 = 25, то полученное частное больше, чем 25. Наименьшее число последовательности, большее 25, есть 27. Таким образом, если следующее за 50 число делится на два, то оно равно 2 x 27 = 54.

2. Оно делится на 3. То же рассуждение. 50 : 3 = 16,7. Первое число последовательности, большее 16,7, есть 18. Если следующее за 50 число делится на 3, то это число равно 3 x 18 = 54.

3. Оно делится на 5. 50 : 5 = 10. Следующее за 10 равно 12,

5 x 12 = 60.

Таким образом, у нас 3 кандидата: 54, 54, 60. Наименьшее из этих трех и есть искомое.

Мы получили 54, используя только уже вычисленную часть последовательности Хэмминга.

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

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

Я предлагаю вам начать с образования различных числовых последовательностей, получаемых вычеркиванием чисел. Вот первые из них:

1 : 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

2 : 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35

3 : 5 7 11 13 17 19 23 25 28 31 35 37 41 43 47 49

На этом уровне можно поверить, что появляется возвратное соотношение: во второй последовательности нет четных чисел, в третьей — нет кратных трем. Образуем следующую: 25, кратное 5 содержится. Покажем механизм перехода от одной последовательности к другой последовательности

3 : 5 7 11 13 17 19 23 26 29 31 35 37 41 43 47 49

5 : 7 11 13 17 23 25 29 81 87 41 43 47

Если вы все это хорошо поняли, то вы теперь должны суметь обобщить. Обозначим черев g(i, j) число, стоящее в последовательности ранга i, которая начинается с g(i, 0). Число g(i, 0) = h(i) и есть счастливое число ранга i. Если вы можете построить g(i + 1, j), исходя ив g(i, …), то вы должны суметь решить задачу. Само собою разумеется, что таблица чисел g не должна участвовать в программе. Это — только промежуточное средство вычисления…

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

Нужно попытаться сгруппировать эффект нескольких последовательных шагов. Нечетное p дает (3p + 1)/2, которое можно еще переписать в виде

3(p + 1)/2 - 1,

что дает правило: добавить 1,

разделить на 2 и умножить на 3,

уменьшить на 1.

Предположим, что результат нечетен. За операцией «уменьшить на 1» сраву же следует операция «добавить 1», и в результате этих двух операций ничто не меняется. Отсюда следует новое правило:

добавить 1,

пока результат четен, делить его на 2 и умножать его на 3,

уменьшить на 1,

делить на 2, пока это возможно.

Составьте по этому правилу программу и заставьте ее перечислять все величины, полученные таким образом (все они будут нечетны. Заметьте, что только первое число в ряду может оказаться кратным трем).

Если вы замените 3 на m, то второе правило изменяется: пока результат четен, делить его на 2 и умножать его на m.

Вернемся к случаю числа 3. Наше правило можно переписать следующим образом: пусть k — некоторое нечетное число; тогда 2^pk - 1 дает (3^pk - 1)/2^q.

Назовем эту операцию переходом p, q.

Можете ли вы показать, что:

если n = 2 по модулю 3, то элемент, следующий за n, равен некоторому элементу, следующему за (2n - 1)/3;

если n дает некоторое n при переходе p, q, где q 1, то число (n - 1)/2 порождает ту же последовательность, что и n, за исключением, быть может, нескольких первых членов.

Любое число вида n = 4k + 1 имеет непосредственно следующее n' n.

Для того чтобы n допускало переход p, 1, необходимо и достаточно, чтобы n имело вид n = k2^p - 1, где

k = 1 по модулю 4, если p нечетно,

k = 3 по модулю 4, если p четно.

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

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

Затем можно пытаться сделать еще один шаг: для любого не вычеркнутого n вычислить первый следующий за ним элемент. Он больше n (в противном случае n был бы вычеркнут). Если он содержится в интервале от 3 до N, то мы ничего не делаем (этот случай будет изучен ниже). Если же он больше N, то мы помещаем его в резерв. Таким образом, мы получим некоторый список чисел, больших N. Если для каждого числа из этого списка возвратная последовательность достигает 1, то мы сможем доказать, что это свойство выполняется для всех чисел, меньших N, и еще для некоторых других.