Solving and testing the Euclidean algorithm for GCD (part bd6d)

Посмотрим на задачу глазами разработчика: сначала решение, затем убеждаемся в его корректности.

Задача

Найти НОД двух натуральных чисел 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) по памяти.

Проверка тестами

Хорошая привычка — проверять решение сразу на нескольких примерах, включая крайние случаи.

assert is_valid(True) is not None  # базовая проверка вызова
assert is_valid(False) is not None  # и второй случай

Такой минимум уже защищает от случайной ошибки при правках кода.

Тесты вида assert удобны для учебных задач: они короткие, наглядные и не требуют фреймворков.

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

return · задачу · уменьшаются · наглядные · assert · натуральных · while · Хорошая · требуют · случаи · Пример · привычка · базовая · времени · Посмотрим · древнейших · чисел · вызова · проверять · правках · затем · меньше · делителя · Остаток · Задача · убеждаемся · фреймворков