Step-by-step: the Euclidean algorithm for GCD (part 2533)

Пройдём задачу шаг за шагом — такой формат удобен для первого знакомства с алгоритмами.

Задача

Найти НОД двух натуральных чисел a и b — классическая задача школьной математики и один из древнейших алгоритмов.

Решение

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


print(gcd(48, 18))

Как это работает

Алгоритм Евклида: НОД(a, b) = НОД(b, a mod b). Остаток всегда меньше делителя, поэтому числа быстро уменьшаются: (48, 18) → (18, 12) → (12, 6) → (6, 0).

Пример работы

6

Сложность

O(log min(a, b)) по времени, O(1) по памяти.

Разбор по шагам

1. Шаг 1. Входные данные. Проверяем, что приходит в функцию, и какие значения считаются корректными.
2. Шаг 2. Основной цикл. Именно здесь происходит вся работа; следим за изменениями переменных на каждой итерации.
3. Шаг 3. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.

Читая чужой код, повторите тот же мысленный разбор по шагам — это самый быстрый способ научиться.

Читайте также:

Результат · математики · работа · соответствует · шагом · задачи · какие · изменениями · print(gcd(48 · Разбор · задача · числа · натуральных · поэтому · условию · работы · Алгоритм · делителя · данные · Именно · Входные · происходит · Основной · алгоритмов · включая · возвращаемое · gcd(a · классическая