На языке C++, задача заключается в сокращении дроби ab. То есть, нужно представить эту дробь в виде cd, где c является

  • 22
На языке C++, задача заключается в сокращении дроби ab. То есть, нужно представить эту дробь в виде cd, где c является целым числом, d - натуральным числом, причем d должно быть минимальным возможным. Вводится два целых числа a и b (-100≤a≤100, 0 < b≤100). Выведите два числа c и d. Пример ввода: 18 27. Пример вывода: 2 3.
Shustr
37
Для решения данной задачи можно воспользоваться алгоритмом Евклида для нахождения наибольшего общего делителя (НОД) чисел \(a\) и \(b\). НОД \(a\) и \(b\) будет равен наибольшему числу, на которое оба числа делятся без остатка.

Процесс нахождения НОД можно представить в виде цикла, где на каждом шаге числа \(a\) и \(b\) заменяются на остаток от деления \(a\) на \(b\) и само число \(b\) соответственно. Цикл продолжается до тех пор, пока \(b\) не станет равным нулю. На этом шаге \(a\) будет равно НОД.

Когда мы найдем НОД \(a\) и \(b\), мы можем сократить дробь \(a/b\) путем деления числителя и знаменателя на значение НОД. Тогда коэффициент \(c\) будет равен \(a/\text{НОД}\), а знаменатель \(d\) будет равен \(b/\text{НОД}\).

Давайте решим задачу на языке C++:

cpp
#include

using namespace std;

int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}

int main() {
int a, b;
cin >> a >> b;

int gcdValue = gcd(a, b);

int c = a / gcdValue;
int d = b / gcdValue;

cout << c << " " << d << endl;

return 0;
}


Для входных данных 18 27 вывод будет следующим:


2 3


Таким образом, дробь 18/27 можно сократить до 2/3. Здесь коэффициент \(c\) равен 2, а знаменатель \(d\) равен 3.