Задачи «А»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида Пример:Введите два числа: 21 14нод(21,14)-7

Задача: найти НОД двух натуральных чисел 21 и 14 с помощью алгоритма Евклида. Пошаговое решение: 1) Пусть a = 21, b = 14. Убедимся, что a ≥ b. 2) Найдем остаток r от деления a на b: 21 = 14 × 1 + 7. Здесь r = 7. 3) Переход к следующему шагу: возьмём пары (a, b) = (14, 7). 4) Найдем остаток: 14 = 7 × 2 + 0. Здесь r = 0. 5) Когда остаток стал 0, НОД равен последнему ненулевому делителю, здесь это 7. Ответ: НОД(21, 14) = 7. Пояснение: - В алгоритме Евклида используется свойство gcd(a, b) = gcd(b, a mod b). Каждый шаг уменьшает одно из чисел, пока остаток не станет нулём. - Для любых чисел слагается, что НОД не меняется при замене пары (a, b) на (b, a mod b); продолжая, в конце получаем наибольший общий делитель. - Временная сложность алгоритма пропорциональна O(log(min(a, b))).