Сколько шагов в нахождении наибольшего делителя в алгоритме Евклида?

Question

[Emelian1917]

Первый шаг алгоритма Евклида при заданных числах m=1 и n=5 повторяется один раз, поскольку остаток от 5/1 равен 0.

При m=2 этот шаг выполняется 5/2 - два раза.
Ну, и далее:
m=3 - 3 раза.
m=4 - 2 раза
m=5 - 1 раз.

Итак, получается ряд чисел 1,2,3,2,1.

Однако, у Кнута в ответе на вопрос, сколько раз повторяется первый шаг алгоритма при n=5 стоит ряд чисел: 2,3,4,3,1.



Ума не приложу почему. Кто ответит?

Первый том, раздел 1.1 задача 6.

Answer 1

[Emelian1917]

Я понял ошибку. Вопрос не в алгоритме расчёта, а в вводимых данных.

Я на автомате в реализации сразу ввожу наибольшее число в делимое, а наименьшее число в делитель. То есть у меня первая операция не 1/5, а 5/1. Соответственно у меня получается на 1 шаг меньше.

Теперь всё в порядке.

Answer 2

[Wataru]

n=5, m=1. первый шаг - поделить, осталось n=1, m=0. Второй шаг - проверить, заметить 0 и остановиться.

n=5,m=3, первый шаг - поделить. осталось n=3, m=2. Второй шаг - опять делим, остается m=2, n=1. Третий шаг - делим, остается n=1, m=0, четвернтый шаг - видим 0, остановились.

для n=m=5 ответ 1, возможно, потому что в алгоритме стоит проверка m==0 || m == n.

Comments

[Emelian1917]

Не думаю, что это верно. Вопрос у Кнута касается количества повторений шага Е1. Сравнение остатка с нулём - это шаг Е2, то есть он не учитывается в количестве повторений.

Я в том числе сделал реализацию алгоритма на C#, и он подтверждает мои расчёты.

public static void E (int m, int n) {
        	Console.WriteLine($"Делим {m} на {n}");
        	T++;
        	int q = m%n;
        	if (q==0) {
        		Console.WriteLine("Наибольший общий делитель " + n);
        		Console.WriteLine("Количество шагов " + T);
        	} else E (n, q);
        }