Question

C++
Визначити рекурсивну функцію обчислення найбільшого спільного дільника
НСД(n, m) натуральних чисел, яка грунтується на співвідношенні НСД(n, m) = НСД(m, r), де
г-залишок від дiлення n на m.

Answer 1

Рекурсивна функція обчислення найбільшого спільного дільника:

int gcd(int n, int m) {

 if (m == 0) {

   return n;

 } else {

   return gcd(m, n % m);

 }

}

Приклад використання функції:

#include <iostream>

int gcd(int n, int m) {

 if (m == 0) {

   return n;

 } else {

   return gcd(m, n % m);

 }

}

int main() {

 int n = 15;

 int m = 10;

 std::cout << "НСД(" << n << ", " << m << ") = " << gcd(n, m) << std::endl;

 return 0;

}