C++ / Довідник функцій

Довідник власних функцій

Функції на основі
алгоритму Евкліда

Знаходимо НСД, НСК та перевіряємо взаємну простоту. Один знайомий алгоритм у чотирьох функціях.

Перевірити функції ↓

Яку функцію обрати

ПотрібноФункціяПриклад
Найбільший спільний дільникGcdOfAB18, 24 → 6
Перевірка взаємної простотиIsMutPrime9, 16 → true
Найменше спільне кратнеLcmofAB18, 24 → 72
НСД і НСК разомMaxDivMinMult18, 24 → 6 та 72

Усі функції призначені для двох натуральних чисел. У наведеному коді використовуй A і B від 1 до 10000. Тоді НСК уміщується у звичний 32-бітний int.

Для недодатних аргументів числові функції повертають −1, логічна функція повертає false. Функція з двома вихідними значеннями записує −1 в обидва результати.

GcdOfAB: найбільший спільний дільник

НСД є найбільшим додатним числом, яке ділить обидва числа без остачі. Використовуємо знайомий алгоритм Евкліда: від більшого віднімаємо менше, доки вони не стануть рівними.

Прототип: int GcdOfAB(int a, int b);

C++
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.

Параметри a та b є копіями аргументів. Їхні зміни всередині GcdOfAB не змінюють початкові змінні main.

З нулем віднімання може зациклитися, тому перевірку додатності виконуємо перед циклом. Для дуже великих чисел цей навчальний спосіб може бути повільним.

IsMutPrime: взаємно прості числа

Два натуральні числа взаємно прості, якщо їхній НСД дорівнює 1. При цьому самі числа не обов’язково прості: 9 і 16 є складеними, але взаємно простими.

Прототип: bool IsMutPrime(int a, int b);

C++
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. Знаходимо його через НСД:

НСК(A, B) = (A / НСД(A, B)) · B

Прототип: int LcmofAB(int a, int b);

C++
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);

C++
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);. Знак & пишемо в заголовку функції, а під час виклику передаємо звичайні змінні. НСД знаходимо лише один раз і використовуємо для НСК.

Другий спосіб: повернути структуру
C++
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
C++
#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.