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

Группировка различных головоломок по темам более или менее условна. Начнем с наиболее простых задач.

ДЛЯ РАЗМИНКИ.

Головоломка 3. Вращающееся число.

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

Это легко…

Та же задача с заменой 5 на 2.

Можно ли заменить здесь 5 какой-нибудь цифрой, отличной от 0?

** Головоломка 4. Квадратный корень.

Извлечь целый квадратный корень с недостатком из очень длинного целого числа (намного более длинного, чем наибольшее целое, которое воспринимается вашим компьютером, например, содержащего 50 или 100 значащих цифр),

Числовые последовательности

Вот две известные в информатике головоломки. Сожалею, что обманываю ожидания своих коллег, которые не найдут здесь ничего нового…

?* Головоломка 5. Последовательность Хэмминга.

Рассмотрим числа, не имеющие других простых делителей, кроме 2, 3 и 5. Расположим их в возрастающем порядке. Это и есть последовательность Хэмминга. Вот ее начало:

2 3 4 5 6 8 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50…

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

?** Головоломка 6. Счастливые числа.

Унтер-офицер собирает своих людей, чтобы решить, кого отправить в наряд на картошку.

«Постройтесь гуськом и рассчитайтесь, начиная с 2». Первый из стоящих говорит 2, следующий — 3, следующий — 4 и т. д.

«Первый в ряду, выйди из строя. Ты освобожден от наряда. Какой у тебя номер?»

«Второй», — отвечает солдат.

«Начиная со второго, рассчитаться по два; тем, кому не выпадет 2, выйти из строя; они пойдут в наряд».

И процесс возобновляется. Первый из вышедших из строя имеет номер 3, и он счастлив: он освобожден от наряда. Теперь рассчитываются по трое, начиная с 3 — с того, кто первым вышел из строя за нарядом…

Составьте программу, выписывающую n первых счастливых чисел для большого n (100, даже 500), Внимание: в чем состоит головоломка: каждый член последовательности должен вычисляться, исходя из данных значений предыдущих счастливых чисел. У вас есть i первых, вычислите следующее. В таблице-то легко вычеркивать… Вот первые счастливые числа:

2 3 5 7 11 13 17 23 25 29

Счастливые числа — не обязательно простыв, а простые числа — не обязательно счастливые…

??? Головоломка 7. Дьявольская последовательность.

Марк Твен описал в своих рассказах жуткую историю. Человек прочел глупые стихи вроде

Кондуктор, отправляясь в путь,
Не рви билеты как-нибудь,
Стриги как можно осторожней.
Чтоб видел пассажир дорожный:

Синий стоит восемь центов,
Желтый стоит девять центов,
Красный стоит только три.
Осторожней режь, смотри!

Припев:
Режьте, братцы, режьте! Режьте осторожно!
Режьте, чтобы видел пассажир дорожный!

(Я цитирую по памяти, но дух соблюден.) Он был порабощен ритмом этих стихов, что стало настоящим наваждением. Если он начинал писать, его перо выводило «Режьте, братцы, режьте». Если он встречал кого-нибудь, он не здоровался с ним, а говорил «Режьте, братцы».

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

Но в воскресенье пастор начал проповедь словами «Режьте, братцы, режьте». Что бы ни было в гимне, который он запевал, слова были одни — «Режьте, братцы, режьте…» Его жизнь стала адом. Он не мог исцелиться, пока в один прекрасный день ему не удалось злодейски обучить этому стихотворению одного профессора университета…

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

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