Задача
Докажите, что число шагов в алгоритме Евклида может быть сколь угодно большим.
Решение
Fn+1 = 1·Fn + Fn–1, то есть Fn–1 – остаток от деления Fn+1 на Fn. Поэтому алгоритм Евклида для вычисления (Fn+1, Fn) содержит n – 1 шаг (последний: F3 = 2F2).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет