Яку функцію обрати
| Потрібно | Функція | Приклад |
|---|---|---|
| Найбільший спільний дільник | GcdOfAB | 18, 24 → 6 |
| Перевірка взаємної простоти | IsMutPrime | 9, 16 → true |
| Найменше спільне кратне | LcmofAB | 18, 24 → 72 |
| НСД і НСК разом | MaxDivMinMult | 18, 24 → 6 та 72 |
Усі функції призначені для двох натуральних чисел. У наведеному коді використовуй A і B від 1 до 10000. Тоді НСК уміщується у звичний 32-бітний int.
Для недодатних аргументів числові функції повертають −1, логічна функція повертає false. Функція з двома вихідними значеннями записує −1 в обидва результати.
GcdOfAB: найбільший спільний дільник
НСД є найбільшим додатним числом, яке ділить обидва числа без остачі. Використовуємо знайомий алгоритм Евкліда: від більшого віднімаємо менше, доки вони не стануть рівними.
Прототип: int GcdOfAB(int a, int b);
int GcdOfAB(int a, int b) {
if (a <= 0 || b <= 0) return -1;
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}GcdOfAB(18, 24) повертає 6. Якщо аргументи однакові, цикл не виконується: GcdOfAB(7, 7) повертає 7.
З нулем віднімання може зациклитися, тому перевірку додатності виконуємо перед циклом. Для дуже великих чисел цей навчальний спосіб може бути повільним.
IsMutPrime: взаємно прості числа
Два натуральні числа взаємно прості, якщо їхній НСД дорівнює 1. При цьому самі числа не обов’язково прості: 9 і 16 є складеними, але взаємно простими.
Прототип: bool IsMutPrime(int a, int b);
bool IsMutPrime(int a, int b) {
if (a <= 0 || b <= 0) return false;
return GcdOfAB(a, b) == 1;
}Перед IsMutPrime розмісти опис GcdOfAB. Приклади: IsMutPrime(9, 16) → true, IsMutPrime(6, 9) → false, IsMutPrime(1, 8) → true.
LcmofAB: найменше спільне кратне
НСК є найменшим додатним числом, яке ділиться і на A, і на B. Знаходимо його через НСД:
Прототип: int LcmofAB(int a, int b);
int LcmofAB(int a, int b) {
if (a <= 0 || b <= 0) return -1;
int g = GcdOfAB(a, b);
return (a / g) * b;
}Для 18 і 24: (18 / 6) · 24 = 72. Спочатку виконуємо ділення, потім множення. Для натуральних чисел A ділиться на їхній НСД без остачі.
Ім’я LcmofAB збережено як в оригіналі. Регістр літер у C++ важливий: використовуй однакове написання в описі та виклику.
MaxDivMinMult: два результати
Функція отримує два вхідні числа та записує НСД і НСК у два вихідні параметри.
Прототип: void MaxDivMinMult(int a, int b, int& nsd, int& nsk);
void MaxDivMinMult(int a, int b, int& nsd, int& nsk) {
if (a <= 0 || b <= 0) {
nsd = -1;
nsk = -1;
return;
}
nsd = GcdOfAB(a, b);
nsk = (a / nsd) * b;
}Виклик: MaxDivMinMult(a, b, nsd, nsk);. Знак & пишемо в заголовку функції, а під час виклику передаємо звичайні змінні. НСД знаходимо лише один раз і використовуємо для НСК.
Другий спосіб: повернути структуру
struct TwoIntNums {
int nsd;
int nsk;
};
TwoIntNums MaxDivMinMult(int a, int b) {
TwoIntNums result;
result.nsd = -1;
result.nsk = -1;
if (a <= 0 || b <= 0) return result;
result.nsd = GcdOfAB(a, b);
result.nsk = (a / result.nsd) * b;
return result;
}Виклик: TwoIntNums answer = MaxDivMinMult(18, 24);. Після цього answer.nsd дорівнює 6, а answer.nsk дорівнює 72. Це альтернативний спосіб отримати ті самі результати.
Перевір функції на двох числах
Спробуй 9 і 16, 7 і 7, 1 і 8.
Повна програма для запуску
Чотири функції та приклад main
#include <iostream>
using namespace std;
int GcdOfAB(int a, int b) {
if (a <= 0 || b <= 0) return -1;
while (a != b) {
if (a > b) {
a = a - b;
} else {
b = b - a;
}
}
return a;
}
bool IsMutPrime(int a, int b) {
if (a <= 0 || b <= 0) return false;
return GcdOfAB(a, b) == 1;
}
int LcmofAB(int a, int b) {
if (a <= 0 || b <= 0) return -1;
int g = GcdOfAB(a, b);
return (a / g) * b;
}
void MaxDivMinMult(int a, int b, int& nsd, int& nsk) {
if (a <= 0 || b <= 0) {
nsd = -1;
nsk = -1;
return;
}
nsd = GcdOfAB(a, b);
nsk = (a / nsd) * b;
}
int main() {
int a, b, nsd, nsk;
cin >> a >> b;
MaxDivMinMult(a, b, nsd, nsk);
cout << nsd << ' ' << nsk << '\n';
if (IsMutPrime(a, b)) {
cout << "yes";
} else {
cout << "no";
}
return 0;
}Для 18 24 відповідь: 6 72, потім no у наступному рядку. Для 9 16: 1 144, потім yes.
Спочатку описано GcdOfAB, бо інші функції викликають її. Усі власні функції розміщено перед main.