Помогите понять код : return NOD(y, x%y)

Question

Помогите понять код : return NOD(y, x%y)

#include <iostream>
using namespace std;

int NOD(int x, int y)
{ if (y == 0) return x;
return NOD(y, x % y);
}

int main()
{
int num, dem;
cout<<"NOMINATOR:\t";
cin>>num;
cout<<"DENOMINATOR:\t";
cin>>dem;
int nod = NOD(num, dem);
cout <<num<< '/' <<dem<< " => " <<(num/nod)<<'/' << (dem/nod)<<endl;

cin.sync();cin.get();
return 0;
}

ВС

Вадим Сазонов

411

18.02.2022

Похожие вопросы

Answer 1 · 2022-02-17 20:08:20

Представьте, что нужно найти наибольший общий делитель по алгоритму Евклида.
Берем два числа, сравниваем, из большего вычитаем меньшее, сравниваем разницу с меньшим.

Пример: НОД 15 и 6.
15 больше, чем 6.
Находим разницу: 15 − 6 = 9
Значит, НОД 15 и 6 равен НОД 9 и 6, найдем его.
Сравниваем 9 и 6.
9 больше, чем 6.
Находим разницу: 9 − 6 = 3
Сравниваем 3 и 6.
3 меньше, чем 6.
Находим разницу: 6 − 3 = 3
Сравниваем 3 и 3.
Числа одинаковые. Следовательно, это и есть НОД.

Другой пример: 1000000 и 12.
1000000 больше, чем 12.
Находим разницу: 1000000 − 12 = 999988
Сравниваем 999988 и 12.
999988 больше, чем 12.
Находим разницу: 999988 − 12 = 999976
…
Так вычитать можно очень долго.
По сути, нам нужно вычитать, пока результат не станет меньше вычитаемого.
Такого результата можно добиться за один шаг, если уменьшаемое поделить на вычитаемое и взять остаток.

Для получения остатка от деления существует операция, называемая «делением по модулю». Ее иногда записывают mod, а в C++ обозначают знаком процента (%).

Примеры:
15 % 6 = 3 (то, что мы получили за две операции вычитания: 15 − 6 и 9 − 6)
16 % 6 = 4
17 % 6 = 5
18 % 6 = 0
1000000 % 12 = 4 (то, что мы могли бы получить за уйму операций вычитания)

Итак, применим усовершенствованный алгоритм Евклида для определения НОД 1000000 и 12.

1000000 больше, чем 12.
1000000 % 12 = 4
Сравним 4 и 12.
12 больше, чем 4.
12 % 4 = 0
Делится без остатка. Значит, НОД 1000000 и 12 равен делителю — 4.

В вашей программе НОД используется для того, чтобы с его помощью сократить дробь, поделив на него числитель и знаменатель.

На всякий случай протестируйте программу с правильными и неправильными дробями.

НХ

Наиль Хабибуллин

53 003

Лучший ответ

17.02.2022

Вадим Сазонов Спасибо за такой развернутый ответ!