Алгоритм Евклида
Наибольший общий делитель двух натуральных чисел не меняется, если заменить пару (a,b) парой (b,a%b).
В этом занятии
- Самостоятельно решить задачу по теме «Алгоритм Евклида» и объяснить проверку результата.
- Напиши программу НОД и проверь пару равных чисел, взаимно простую пару и случай, когда одно делится на другое.
Пригодится: informatics8-for-range
Разберёмся перед практикой+
Алгоритм Евклида
Наибольший общий делитель двух натуральных чисел не меняется, если заменить пару (a,b) парой (b,a%b). Повторение заканчивается при нулевом втором числе, и первое становится ответом. Остаток уменьшается, поэтому процесс не продолжается бесконечно.
В Python запись a,b=b,a%b вычисляет обе правые части по старым значениям. Два отдельных присваивания без временной переменной могут испортить вычисление остатка. Для проверки выпиши пары и убедись, что ответ делит оба исходных числа.
(30,18)→(18,12)→(12,6)→(6,0), поэтому НОД равен 6.
- Замени пару на делитель и остаток.
- Остановись при нулевом остатке.
Открываем цифровую мастерскую…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Напиши программу НОД и проверь пару равных чисел, взаимно простую пару и случай, когда одно делится на другое.
- Сначала предположите результат, затем проверьте и объясните, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.