Программирование игр и головоломок
Шрифт:
Нет никакой надежды, что вам удастся доказать, что для любого нечетного числа в качестве начального значения последовательность достигает единицы.
Но в высшей степени увлекательно составить эту крошечную программу и посмотреть, как она работает. Испытайте число 27 в качестве начального значения: вы получите очень длинную последовательность, среди элементов которой есть 9232. Если вы изучите ряды чисел, получаемые для начальных значений, взятых среди нечетных целых от 3 до 99, вы получите довольно много патологических последовательностей, не всегда сильно отличающихся. Все это очень смущает. Ни один специалист по теории чисел еще не смог Доказать, что такая
Эта программа замечательно иллюстрирует то, что называется «проблемой остановки». Существуют простейшие программы, относительно которых нет уверенности, что они остановятся…
Теперь, когда вы уже познакомились с этой последовательностью, получите предмет головоломки. Заметим сначала, что если 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]
Конечно, конечно. Почему бы не послать им еще денег? Та же задача:
4
«Пришлите побольше денег.»
5
«Помогите молодому человеку.»
HELP + THE = YOUNG
Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?
DEVOIR, LECON, 'EL`EVE. [6]
Есть аналогичные зашифрованные сложения по-французски. Например, такая:
'EL`EVE + LECON = DEVOIR
? Головоломка 10. Зашифрованное умножение.
Довольно сложений, это становится скучным. Вот зашифрованное умножение:
6
«Нужно, лекция, ученик.»
ABCDE * 9 = FGHIJ
Здесь 10 букв представляют 10 различных цифр, так что одна из них равна 9. Можно сразу кое-что сказать о возможных значениях букв, но чтобы получить решение, придется идти буквально ощупью. Столько же придется искать и компьютеру.
?* Головоломка 11. Забавное число.
Число 123456789 обладает забавными свойствами:
123456789 * 2 = 246913578
Как и исходное, удвоенное число образовано всеми девятью цифрами, кроме 0.
123456789 * 4 = 493827156
Результат снова образован девятью цифрами, отличными от 0.
123456789 * 5 = 617283945
По-прежнему 9 цифр.
123456789 * 7 = 864197523
Опять 9 цифр, и это еще не все.
123456789 * 8 = 987654312
Но это не работает ни для 3, ни для 6. Это не может работать и для 9, потому что в результате больше 9 цифр,
Тем не менее есть много чисел, образованных всеми 9 цифрами (кроме 0), которые после умножения на 3 дают результат, образованный теми же девятью цифрами. Можете ли вы дать список всех таких чисел, оканчивающихся на 9? И также список тех, которые кончаются на 3?
Можно ли распространить использованный метод на случай умножения на 6?
Доказательства теорем
Компьютер можно использовать для доказательства теорем. Это — трудная задача искусственного интеллекта. Мы снабжаем компьютер правилами вывода, даем формулировку того, что требуется доказать, и исходные аксиомы. Компьютер пытается найти последовательность правил вывода, которые могут привести от исходных данных к требуемым рёзультатам.