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

Я предложил вам алгоритм без доказательства. Поэтому попытайтесь его проверить…

Я предложил вам алгоритм для десятичной системы счисления. Можно предложить похожий алгоритм для двоичной системы. Тогда не возникнет цикл вычитаний последовательных нечетных чисел из каждого куска, поскольку в куске есть только одно нечетное число: 1. Алгоритм упрощается: если можно вычесть нечетное число — мы его вычитаем, в противном случае мы не делаем ничего. Затем сдвигаем, добавляем 1 и приписываем 1 в конце… Этот алгоритм намного легче реализовать. Но тогда нужно сначала перейти к основанию 2, а затем преобразовать двоичный результат в десятичный. Вам следует посмотреть, что более эффективно…

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

Аккуратно поставим задачу. То, что от вас требуется, — это не взятая глобально последовательность, а вот что: если начало последовательности выписано, то нужно найти следующее число. Возьмем пример, данный в головоломке 5: какое число следует за 50?

Есть ровно три возможности.

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, вы можете пробежать все нечетные числа в возрастающем порядке и проверить, что для каждого ив них это верно. Но вы можете сначала вычеркнуть из списка все нечетные числа, о которых вы знаете, что их поведение сводится к поведению последовательности, относящейся к меньшему нечетному числу, поскольку список нечетных чисел пробегается в возрастающем порядке, и этот случай уже был неучен. Таким образом, остается не больше чисел, чем уже было отмечено.