C++ / Цикли з умовою

Тема 5. Цикли з умовою

Найбільший спільний дільник
Алгоритм Евкліда

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

Побачити алгоритм у дії ↓

Крок 1

Що таке найбільший спільний дільник

Дільник числа ділить його без остачі. Наприклад, 6 є дільником 18, бо 18 % 6 = 0.

Дільники 18: 1, 2, 3, 6, 9, 18.
Дільники 24: 1, 2, 3, 4, 6, 8, 12, 24.

НСД(18, 24) = 6
Це найбільше додатне число, на яке без остачі діляться обидва числа.

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

Крок 2

Алгоритм Евкліда через віднімання

Поки два числа різні, від більшого віднімаємо менше. Коли числа стануть рівними, будь-яке з них і буде їхнім НСД.

ЧислаДіяПісля дії
18 і 2424 − 18 = 618 і 6
18 і 618 − 6 = 1212 і 6
12 і 612 − 6 = 66 і 6

Отримали однакові числа. Отже, НСД(18, 24) = 6.

Чому цей спосіб працює

Спільні дільники двох чисел не змінюються, якщо від більшого відняти менше. Наприклад, дільники, спільні для 24 і 18, також спільні для 18 і 6. Обидва числа залишаються додатними, а їхня сума щоразу зменшується, тому повторення завершаться.

У цьому способі обидва початкові числа мають бути більшими за 0. Якщо одне число дорівнює 0, віднімання нуля нічого не змінить і цикл може не завершитися.

Крок 3

Виконай алгоритм крок за кроком

Введи два натуральні числа й натискай «Одне віднімання». Смужки показують, як зменшуються поточні числа.

Для наочності тренажер приймає числа від 1 до 100.

Поточне x:

Поточне y:

КрокДіяxy

Спробуй 12 і 12: числа рівні від початку, тому віднімання взагалі не потрібні. Спробуй 9 і 16: у кінці обидва числа стануть рівними 1.

Крок 4

Програма на C++

Введені a і b зберігаємо. Змінюємо лише їхні копії x та y, щоб початкові числа залишилися доступними після циклу.

C++
#include <iostream>
using namespace std;

int main() {
    int a, b, x, y;
    cin >> a >> b;
    x = a;
    y = b;
    while (x != y) {
        if (x > y) {
            x = x - y;
        } else {
            y = y - x;
        }
    }
    cout << x;
    return 0;
}

Для 18 24 програма виведе 6, для 9 16 виведе 1. Вводимо додатні числа, що вміщуються в int.

Тут зручно використати while: спочатку перевіряємо, чи числа різні. Якщо вони вже рівні, тіло циклу не виконується. У C++ нерівність записуємо як !=, а рівність для перевірки як ==.

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

Крок 5

Як використати знайдений НСД

МетаЩо робимо після знаходження g = НСД(a, b)
Перевірити взаємну простотуПеревіряємо g == 1
Скоротити дріб a / bНовий чисельник a / g, знаменник b / g
Знайти НСК(a / g) * b
Знайти НСД трьох чиселСпочатку НСД(a, b), потім НСД отриманого результату та c

Наприклад, дріб 18/24 скорочується на 6: отримаємо 3/4. Найменше спільне кратне 18 і 24: (18 / 6) · 24 = 72.

У формулі НСК краще спочатку поділити, а потім помножити. Для добутків і додавання дробів використовуй невеликі значення або цілий тип long long, який вміщує більші числа.

Крок 6

Уточнення до варіантів

Варіанти 3 і 4 задані для цілих чисел. Від’ємні значення спочатку заміни на протилежні, наприклад: if (x < 0) x = -x;. Використовуй невеликі вхідні значення.

Нульові значення перевір окремо до запуску віднімання: якщо лише одне число дорівнює 0, пара взаємно проста тільки тоді, коли модуль іншого дорівнює 1. Пара 0 і 0 не є взаємно простою.

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

Щоб скоротити дріб, чисельник і знаменник потрібно поділити на їхній НСД. Формулювання «не мають спільних дільників» слід розуміти як «не мають спільних дільників, крім 1».

Крок 7

Варіанти для самостійної роботи

Нумерацію й повторювані варіанти збережено.

Варіант 5

Дано натуральні числа a і b, що позначають чисельник та знаменник звичайного дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, крім 1, і задовольняють рівність a / b = p / q . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.

↑ До вибору варіанта

Варіант 6

Дано натуральні числа a і b, що позначають чисельник та знаменник звичайного дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, крім 1, і задовольняють рівність a / b = p / q . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.

↑ До вибору варіанта

Варіант 7

Знайдіть суму двох звичайних дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких, що a / b + c / d = p / q. Пояснення: додати два дроби. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.

↑ До вибору варіанта

Варіант 8

Знайдіть суму двох звичайних дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких, що a / b + c / d = p / q. Пояснення: додати два дроби. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.

↑ До вибору варіанта

Варіант 9

Знайдіть найбільший спільний дільник трьох натуральних чисел за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).

↑ До вибору варіанта

Варіант 10

Знайдіть найбільший спільний дільник трьох натуральних чисел за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).

↑ До вибору варіанта

Варіант 15

Знайдіть всі правильні звичайні дроби, що не скорочуються, знаменники яких не більше 5 (дріб задається двома натуральними числами; чисельником та знаменником). Відповідь: 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5

↑ До вибору варіанта

Варіант 16

Знайдіть всі правильні звичайні дроби, що не скорочуються, знаменники яких не більше 7 (дріб задається двома натуральними числами; чисельником та знаменником). Відповідь: 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7

↑ До вибору варіанта

Варіант 17

Дано натуральні числа m, n1, n2, ...,nm (m>=2). Обчисліть НСД(n1,n2,...,nm ), використовуючи співвідношення НСД(n1,n2,...,nm)=НСД(НСД(n1,n2,...,nm-1),nm) та алгоритм Евкліда. Пояснення: числа вводити у циклі, ввести два числа, знайти для них НСД, ввести третє число, знайти НСД для третього числа та знайденого НСД перших двох чисел, ввести четверте число і т.д. поки не будуть введені всі числа.

↑ До вибору варіанта