Программирование игр и головоломок
Шрифт:
Число, полученное при обращении порядка цифр, равно
1000d + 100c + 10b + a,
и разность этих двух чисел равна
999 (a– d) + 90 (b– c).
Числа a, b, c, d были расположены в невозрастающем порядке, и они не все равны между собой, так что a строго больше d и a– d не равно нулю. Все остальное просто.
Головоломка 16.
Единственное,
Головоломка 17.
Эта программа основана на следующих результатах:
если b нечетно, n четно, то n делится на b тогда и только тогда, когда n/2 делится на b;
нечетное n делится на b тогда и только тогда, когда n– b делится на b. Но n– b четно.
Для n = 277– 3 и b = 7 вы получаете:
Число n нечетно. Рассматриваем n– b = 277– 10. Оно делится на 2: получаем 276– 5.
Это число нечетно: (276– 5) - 7 = 276– 12.
Делим на 4: 274 — 3.
Получаем ту же самую задачу, в которой показатель уменьшен на 3. Так как 77 = 3*25 + 2, то мы таким образом доходим до 22 — 3 = 1, которое не делится на 3. Вряд ли вас слишком утомит доказательство того, что 2n– 3 никогда не делится на 7…
Головоломка 18.
Я не в состоянии рассказать вам, как я получил эту программу, это — очень долгая история, связанная с разложением целых чисел на множители. Может быть, когда-нибудь я ее и опубликую. Следовательно, будем разбираться в том, что нам дано — в тексте программы.
Начнем с нечетного n. В соответствии с инициализацией программы n = 4p– 1, где p четно. В противном случае уже последует ответ «НЕТ». Следовательно, рассмотрите нечетное n, являющееся полным квадратом и, следовательно, квадратом нечетного числа 2k + 1;
(2k + 1)2 = 4k2 + 4k + 1 = 4k (k + 1) + 1.
Так как k (k + 1) — произведение двух последовательных целых чисел, и из двух последовательных целых чисел всегда есть хотя бы одно четное число, получаем простой, но интересный результат: любой квадрат нечетного числа сравним с 1 по модулю 8. Таким-образом, при n отличном от 1 по модулю 8 инициализирующая часть программы выводит, что n не является точным квадратом.
Посмотрим теперь, что происходит внутри цикла. Делим p на 2, и если результат четен, мы удовлетворяемся тем, что умножаем a
на 2. При этом действии произведение a*p остается постоянным. Поэтому кажется вероятным, что в цикле существует инвариантная величина, запись которой содержит a*p в предположении, что p четно.Если после деления p на 2 результат оказывается нечетным, то мы вычитаем из этого результата a/2 + b. Обозначим новые значения a, b, p через а', b', p' соответственно:
а' = 2*а, p' = p/2 - а/2 - b, b' = a + b.
Для этих значений получаем:
a'*p' = a*p– a2– 2a*b = а*р– (а + b)2 + b2 = а*р– b'2 + b2.
Это, наконец, дает
а'*p' + b'2 = а*р + b2.
Инвариантной величиной цикла оказывается, таким образом, сумма ар + b2, причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.
В начале а = 4, p (целая часть дроби (n– 1)/4) четно, b = 1, так что ар + b2 = n.
Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.
Тогда при переходе от a, b, p к a', b', p' либо
b' = b, а' = 2*а, так что если b < а, то и b' < а';
либо
b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.
Следовательно, вот ситуация, которую цикл оставляет инвариантной: