Элементы теории чисел и криптозащита. Воронков Б.Н - 23 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

23
последовательной парой, первоначально a/b < c/d, скажем, помещают меди-
анту (a + b)/(b + d), а затем отбрасывают некоторую дробь, для которой b +
+ d > n + 1.
5.4. Ним Фибоначчи. Напишите программу для представления неко-
торого числа m в «системе Фибоначчи», т. е., в виде суммы различных и не-
смежных чисел Фибоначчи. Эти числа (названные в честь Фибоначчи – это
вымышленное имя Леонардо из Пизы (1180–1228)) определяются как f
1
= 1,
f
2
= 1, f
n
= f
n–1
+ f
n–2
для n ≥ 3. Таким образом, последовательность начинает-
ся таким образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . Например, число 54 мо-
жет быть записано как сумма 34 + 13 + 5 + 2: здесь представлены все числа
Фибоначчи и отсутствуют два, входящие в последовательность Фибоначчи
f
i
. Идея заключается в вычитании из m наибольшего f
i
≤ m, а затем из m – f
i
наибольшего f
j
≤ m – f
i
, и т. д.
Теперь рассмотрим следующую игру между двумя игроками, которые
берут фишки попеременно из одной кучи, состоящей из n фишек. Первый
игрок может набрать некоторое количество фишек m
1
< n фишек; второй
может взять некоторое другое количество фишек m
2
, где 0 < m
2
≤ 2m
1
. На
выбор игрокам: каждый может, по крайней мере, взять одну фишку и не бо-
лее двух раз предшествующего крупного «куша». Выигрывает тот, у кого
последняя взятка.
Стратегия такова. Если число фишек на каком-либо этапе не является
числом Фибоначчи, тогда это выражается в виде суммы чисел Фибоначчи, как
описано ранее,
например, 54 = 34 + 13 + 5 + 2. Другой игрок стремится скорее
сбросить, нежели взять, некоторое число малых членов из разложения, обес-
печивая им итог меньший, чем половина следующего большего члена. Таким
образом, из кучи, состоящей из 54 фишек, этот игрок может взять только 2, а
не 2 + 5 = 7, так как 2 × 7 > 13, а другой игрок может взять только 13 и оста-
вить количество
фишек, равное числу Фибоначчи, а именно, 34.
Напишите программу розыгрыша нима Фибоначчи.
5.5. Обратные палиндромы. Пример: 87 + 78 = 165, 165 + 561 = 726,
726 + 627 = 1353, 1353 + 3531 = 4884. Результат является палиндромом, то
есть, читается в обратном порядке так же, как и в прямом. Напишите про-
грамму выбора чисел вплоть до, скажем, 999, и повторите вышеприведен-
ные операции, пока число не станет либо палиндромом, либо слишком
большим. Многие числа формируют палиндром очень быстро; испытайте
187 как начальное число, как
пример, где это не выполняется.
Составьте таблицу результатов в виде числа ступеней, взятых для ка-
ждого начального числа. (Согласно [7] только 75 из 900 трёхзначных чисел
требуют более пяти обращений и все числа < 10 000 произвели палиндром
случайно, за исключением 196, с которым даже не произвело ни одного!).

Страницы