номер 16, страница 61 - гдз по информатике 8 класс учебник Котов, Лапо

16 Измените функцию nod из примера 7.14 так, чтобы наибольший общий делитель вычислялся следующим образом:

пока $a > 0 \text{ and } b > 0$

если $a > b$

замени $a$ остатком от деления на $b$

иначе замени $b$ остатком от деления на $a$

результат $a + b$

* Почему предложенный алгоритм можно использовать для вычисления НОД?

Решение:

Перепишем функцию nod(a, b) на языке Python в соответствии с предложенным псевдокодом через деление с остатком:

def nod(a, b): while a > 0 and b > 0: if a > b: a = a % b else: b = b % a return a + b

Пример вызова функции для проверки:

print(nod(48, 18)) # выведет 6

Ответ на дополнительный вопрос:

Этот алгоритм представляет собой оптимизированный вариант классического алгоритма Евклида, основанный на следующих свойствах делимости:

• Если большее число заменить на остаток от его деления на меньшее число, то наибольший общий делитель пары чисел не изменится: $\text{НОД}(a, b) = \text{НОД}(a \pmod b, b)$ при $a > b$. Деление с остатком позволяет намного быстрее уменьшать числа, чем последовательное вычитание (мы как бы за один шаг вычитаем меньшее число сразу максимальное количество раз).
• Цикл завершается в тот момент, когда одно из чисел делится нацело на другое, и остаток от деления становится равным $0$. Второе число при этом равно искомому наибольшему общему делителю, так как $\text{НОД}(x, 0) = x$. Сумма a + b позволяет вернуть именно то число, которое осталось ненулевым, без написания дополнительного условия.