Складання програми для обчислення НСД двох чисел

Практична робота 11

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

Обладнання: комп’ютер із середовищем програмування мовою Python.

Теоретична частина

Евклід (бл. 325 — бл. 270 до н. е.) — давньогрецький математик, автор перших теоретичних трактатів із математики, що дійшли до сучасності.

Хід роботи

Під час роботи за комп’ютером дотримуйтеся правил безпеки.

1. Завантажте програму: Python → IDLE і створіть файл із назвою Pract11.

2. Проаналізуйте алгоритм обчислення НСД чисел А і B: поки А ≠ В, від більшого числа віднімати менше.
Блок-схему подано на рисунку.

6. Запишіть програмний код у вікні програми, виконайте програму для значень, наведених у п. 3.

8. Додайте до програмного коду команди для обчислення значення найменшого спільного кратного (НСК) уведених чисел.
Як відомо НСК(а, b) = а*b/НСД(а, b). У процесі обчислення НСД значення змінних a і b змінюються. Щоб пізніше використати початкові значення для обчислення НСК(a, b), відразу після введення їх слід зберегти в інших змінних, наприклад, a1 і b1.

10. Внесіть зміни у текст програми у програмному вікні.
Збережіть файл і запустіть програму на виконання. Перевірте роботу програми.

12. Закінчіть роботу, закривши вікно IDLE.

Зробіть висновок: як складати та виконувати циклічні алгоритми для розв’язування задач.