НОД, НОК и Фибоначчи

Наибольший общий делитель

НОД (наибольший общий делитель) двух чисел — самое большое число, на которое делятся оба. Например, НОД(12, 18) = 6, потому что 6 — крупнейший общий делитель. НОД нужен, чтобы сокращать дроби и решать задачи на делимость.

Самый известный способ его найти — алгоритмЧёткая последовательность шагов для решения задачи за конечное число действий. Евклида, придуманный более двух тысяч лет назад. Идея: НОД(a, b) равен НОД(b, a % b). Мы заменяем большее число на остаток от деления, пока второе число не станет нулём — тогда первое и есть ответ.

Проследим gcd(48, 36): пара (48, 36) → (36, 48%36=12) → (12, 36%12=0). Как только b стало 0, возвращаем a = 12. Каждый шаг быстро уменьшает числа, поэтому алгоритм работает молниеносно даже для огромных значений.

Наименьшее общее кратное

НОК (наименьшее общее кратное) — наименьшее число, которое делится на оба. Его не нужно искать перебором: есть формула, связывающая НОК и НОД — НОК(a, b) = a * b // НОД(a, b).

Факториал и Фибоначчи без рекурсии

В модуле про рекурсиюПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились. мы считали факториал и Фибоначчи, вызывая функциюИменованный блок кода, который можно вызывать многократно. Может принимать аргументы и возвращать результат. из самой себя. Но те же задачи решаются обычным циклом — и часто быстрее и без риска переполнить стек вызовов. Итеративный Фибоначчи особенно хорош: он держит лишь два последних числа и идёт за один проход.

Напечатается [0, 1, 1, 2, 3, 5, 8]. В отличие от наивной рекурсии, этот вариант не пересчитывает значения заново — он линейный и легко считает fib(1000).

⚠️ Частые ошибки новичков

Ошибка. В алгоритме Евклида перепутать порядок присваивания и написать сначала a = b, а потом b = a % b двумя строками — тогда к моменту второй строкиТекстовое значение в кавычках: "привет". Неизменяема. По-английски string (str). a уже испорчено. Множественное присваивание a, b = b, a % b вычисляет правую часть целиком до записи и избавляет от этой ловушки. Запустите сломанную версию и сравните.