Программирование игр и головоломок - Жак Арсак

Мы получили 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 — некоторое нечетное число; тогда 2pk − 1 дает (3pk − 1)/2q.

Назовем эту операцию переходом 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 = k2p − 1, где

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

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

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

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

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

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

Вот, наконец, последнее свойство, которое вы должны уметь доказывать: не существует пар p, q, где p и q — натуральные числа, для которых n дает n при переходе p, q. Это не означает, что не существует периодических последовательностей. Про них я сумел доказать только тот факт, что не может иметь места цикл

n дает n' при переходе p, q;

n' дает n при переходе p', q'.

Как бы то ни было, этого на сей раз недостаточно.

Но это полезно, чтобы увидеть, каким образом 3 играет существенную роль в этом деле…

Зашифрованные операции

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

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

Пусть даны значения D и E (значения различны). Из них получается Y и то, что «в уме». По этой величине «в уме» получается значение N. Так как N + R + «в уме» = E (плюс, быть может, 10) и так как E известно, то только N можно выбирать произвольно. Кроме того, нужно, чтобы оно отличалось от D, E и Y и нужно, чтобы R, полученное таким образом, отличалось от D, E, Y, N. Если пока все идет хорошо, то вы продолжаете выбор. Если уже возникла невозможность, то вернитесь назад и осуществите другой выбор N. Если никакой выбор для N не оказывается возможным, вернитесь назад и измените выбор E…

Это — одно решение.

Но оно может потребовать много времени. Чтобы выиграть время, ограничьте возможные выборы. Очевидно, что значение SEND ограничено числом 9999, как и MORE, и поэтому значение MONEY не может превосходить 19998. Так как это — число из пяти цифр, то M = 1. Это освобождает вас от испытания 1 для D и E. Если цифра единиц суммы D + E равна 1, то этот набор D и E недопустим.

Поставьте 1 на свое место:

S + 1 + «то, что в уме» дает число, большее девяти. Это возможно только в случае, если мы предположим что «в уме» для S кое-что есть:

S + 2 = 10 + O

(справа буква O, а не цифра ноль).

S + 2 может превосходить 9 только в случае, если S больше 7. Единственные возможные значения — это

S = 8, что дает букве O значение 0,

S = 9, что дает букве O значение 1.

Но 1 уже присвоено букве M. Следовательно, S = 8 и O = 0.

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

1. Берем первую комбинацию.

2. Испытываем ее. Если она удовлетворяет требованиям, запоминаем ее значение.

3. Если это — последняя комбинация, то все значения записаны и все кончено.

4. Если не последняя, то переходим к следующей комбинации и повторяем, начиная с пункта 2.

В данном случае — так как мы уже знаем значения букв S, O, M, остается только три еще не определенных значения: D, E, N. Для каждой из них берем постепенно возрастающие значения, изменяя их таким образом, чтобы сначала возрастало N при постоянных D и E. Затем меняется E при постоянном D (а N пробегает все возможные значения). Когда все возможные значения для E испытаны, мы переходим к следующему значению D.