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

Можно обобщить предыдущий алгоритм, используя свойства десятичной записи чисел. Данное число разделяется на куски по две цифры, начиная справа; затем мы начинаем вычитать последовательные нечетные числа из крайнего слева куска:

Если это нельзя продолжать дальше, то последнее вычитаемое число увеличивается на единицу, сдвигается на один шаг вправо, и следом за ней приписывается единица. Это — первое нечетное число, которое следует вычитать из предыдущего остатка.

В приведенном выше примере 7 + 1 = 8; приписывая 4, получаем 81 и продолжаем:

Поскольку продолжать дальше нельзя (последнее возможное вычитание из остатка — это крайнее справа), то последнее из вычитаемых чисел нужно увеличить на 1, а затем разделить на 2, чтобы получить корень. Последний остаток и есть остаток квадратного корня:

85 + 1 = 86, 86/2 = 43,

1909 = (43)² + 60.

Этот алгоритм достаточно прост для программирования при длинных числах, и он дает вполне разумное время вычисления.

У вас много возможностей представлять свои данные. Так как мы оперируем с кусками из двух цифр, то вы можете задавать свои данные таблицами целых чисел в интервале от 0 до 99.

Вы можете представлять свои целые числа как цепочки символов, где используются только числовые символы (цифры) от 0 до 9. Выбор способа зависит от ваших предпочтений и от возможностей вашей машины оперировать с таблицами и цепочками. Тщательно рассмотрите, какие операции нужно сделать. Вы ничем не ограничены: почему бы не запрограммировать и сравнить два разных решения?

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

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

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

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

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

1. Число делится на 2. После однократного деления на 2 оно не будет иметь других делителей нуля, кроме 2, 3 и 5. Следовательно, это число — из последовательности. Так как 50 : 2 = 25, то полученное частное больше, чем 25. Наименьшее число последовательности, большее 25, есть 27. Таким образом, если следующее за 50 число делится на два, то оно равно 2 ? 27 = 54.

2. Оно делится на 3. То же рассуждение. 50 : 3 = 16,7. Первое число последовательности, большее 16,7, есть 18. Если следующее за 50 число делится на 3, то это число равно 3 ? 18 = 54.

3. Оно делится на 5. 50 : 5 = 10. Следующее за 10 равно 12,

5 ? 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;