Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск наибольшего общего делителя на Python
Пора вернуться к моей любимой теме - алгоритмы.
Сегодня алгоритм поиска НОД, т.е. наибольшего общего делителя.
Начнём с универсального подхода для произвольного количества целых чисел.
Программу см. ниже. Алгоритм весьма прост. Берём наименьшее из списка число и начинаем проверять на делимость начиная с него. Если это не НОД, то берём его половину, а далее уменьшаем возможный НОД каждый раз на единицу, пока не доберёмся до нужного значения. Работу функции map() и метода split(), надеюсь, не забыли? Алгоритм правда не допускает значение 0, но можете его подправить.
Теперь обратимся к алгоритму Эвклида для двух чисел a и b. Словесно это выглядит так:
- Большее число делим на меньшее.
- Если делится без остатка, то меньшее число и есть НОД (выходим и печатаем).
- Если остаток не ноль, то большее число заменяем на остаток от деления.
- Повторяем начиная с пункта 1.
Ну а теперь несколько реализация этого алгоритма.
Пример номер 1. Это, скажем так, наиболее понятная реализация
Пример 2. Пытаемся сократить текст программы
Пример 3. А слабо ещё сократить?
Варианты, конечно, я не исчерпал. Вот ещё один вариант - рекурсивный. Основан, в частности, на том свойстве, что если искать остаток от деления меньшего числа на большее, то результат будет равен меньшему числу. Красиво!
И это ещё не всё, но пора заканчивать.
В библиотеке math, кстати, есть функция gcd(), посмотрите.
Также гляньте статью о НОК.
Пишите свои предложения и замечания и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
