Рекурсивный алгоритм нахождения НОД двух натуральных чисел
Всем привет! Сегодня я хотел бы поделиться с вами рекурсивной функцией нахождения наибольшего общего делителя (НОД) двух натуральных чисел. В качестве алгоритма мы будем использовать модифицированный алгоритм Евклида. Для примера возьмем два числа⁚ 7006652 и 112307574, и найдем их НОД.Шаг 1⁚ Задаем два натуральных числа. В нашем случае это 7006652 и 112307574.
Шаг 2⁚ Проверяем, равно ли одно из чисел нулю. Если да, то НОД равен другому числу. Если нет, переходим к следующему шагу.
Шаг 3⁚ Делим большее число на меньшее по модулю и сохраняем остаток деления.
7006652 % 112307574 7006652
Шаг 4⁚ Теперь меняем местами числа таким образом, чтобы остаток от деления стал меньшим числом, а само число – большим.
112307574 % 7006652 474238
Шаг 5⁚ Повторяем шаги 3 и 4 до тех пор٫ пока одно из чисел не станет равным нулю.
Шаг 6⁚ Когда одно из чисел станет равным нулю, тогда другое число будет являться НОД. В нашем случае НОД равен 1234.
Рекурсивная функция⁚
cpp
int gcd(int a, int b)
{
if (b 0)
return a;
return gcd(b, a % b);
}
Теперь, используя эту рекурсивную функцию, мы можем легко найти НОД любых двух натуральных чисел.
Пример использования функции⁚
cpp
#include
int gcd(int a, int b);
int main
{
int a, b;
std⁚⁚cout << ″Введите два натуральных числа⁚ ″;
std⁚⁚cin >> a >> b;
int result gcd(a, b);
std⁚⁚cout << ″НОД(″ << a << ″, ″ << b << ″) ″ << result << std⁚⁚endl;
return 0;
}
int gcd(int a, int b)
{
if (b 0)
return a;
return gcd(b, a % b);
}
Введите два натуральных числа⁚ 7006652 112307574
НОД(7006652, 112307574) 1234
Я надеюсь, что это решение поможет вам в нахождении НОД двух натуральных чисел в вашем коде. Не бойтесь использовать рекурсивные функции ─ они могут существенно упростить вашу работу и сделать код более понятным.