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

Последовательность определяется следующим образом: первый член этой последовательности есть произвольное нечетное число, отличное от единицы. Следующее за числом p равно

p /2, если p четно,

З p + 1, если p нечетно.

Последовательность заканчивается, когда в ней встречается значение 1.

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

7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

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

Но в высшей степени увлекательно составить эту крошечную программу и посмотреть, как она работает. Испытайте число 27 в качестве начального значения: вы получите очень длинную последовательность, среди элементов которой есть 9232. Если вы изучите ряды чисел, получаемые для начальных значений, взятых среди нечетных целых от 3 до 99, вы получите довольно много патологических последовательностей, не всегда сильно отличающихся. Все это очень смущает. Ни один специалист по теории чисел еще не смог Доказать, что такая последовательность принимает значение 1 для любого начального значения. Не больше известно и о том, почему некоторые из этих последовательностей — короткие, а другие — слишком длинные…

Эта программа замечательно иллюстрирует то, что называется «проблемой остановки». Существуют простейшие программы, относительно которых нет уверенности, что они остановятся…

Теперь, когда вы уже познакомились с этой последовательностью, получите предмет головоломки. Заметим сначала, что если p нечетно, то мы переходим к З p + 1 — числу, отличному от 1. Очевидно, что непосредственно предшествующий шаг есть деление на 2. Поэтому можно изменить правило построения последовательности описанным ниже образом: следующее за числом p равно

p /2, если p четно,

(З p + 1)/2, если p нечетно,

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

7 11 17 26 13 90 10 5 8 4 2 1

Вы можете пойти еще дальше в том же направлении, объединяя вместе все последовательные шаги, действующие по правилу (З p + 1)/2, и все следующие за ними шаги, состоящие в делении на два. Вы получите два новых правила перехода, гораздо более уплотненные. Свяжите их и пустите в ход. Для числа 7 вы должны без задержки получить последовательность

7 13 5 1

Это позволяет рассматривать обобщения задачи. Пусть k — нечетное число. Возьмем в качестве правил перехода следующие:

p /2, если p четно,

k * p + k − 2, если p нечетно.

Возможно уплотнение, аналогичное предыдущему. Для k = 5 следующее за числом 3 есть 3, и существуют исходные точки, для которых программа не останавливается. Для k = 7 она идет точно так же. Так что проблема остановки связана со свойством числа k . Я бы здесь… Впрочем, мало ли чего я хочу!

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

Головоломка 8.SEND MORE MONEY. [4] «Пришлите побольше денег.»

Это — лаконичная телеграмма английского студента своему отцу. История умалчивает о том, как отец это принял и были ли отправлены деньги…

SEND + MORE = MONEY

Программа очень легкая. Время вычисления короткое. Едва ли это головоломка. Как раз для тренировки…

Головоломка 9.HELP THE YOUNG. [5] «Помогите молодому человеку.»

Конечно, конечно. Почему бы не послать им еще денег? Та же задача:

HELP + THE = YOUNG

Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?