☰ Содержание · Информатика

Локальные и глобальные переменные, функция НОД (EKUB)

Уроки 49–50 · 2 урока · М. Р. Файзиева, Д. М. Сайфуров, Н. С. Хайтуллаева. Информатика и информационные технологии, 9 класс. «Nashriyot uyi Tasvir», Ташкент, 2020
50

Практическое занятие: функции и алгоритм Евклида

Учебник: с. 98–99
ЦельНа практическом занятии находит наибольший общий делитель (НОД, EKUB) двух чисел по алгоритму Евклида, записывает его в виде функции и использует её для сокращения дроби и нахождения наименьшего общего кратного (НОК, EKUK).
Новые слова
НОД (EKUB): наибольший общий делитель двух чисел (gcd) · EKUBалгоритм Евклида: повторять (a, b) → (b, a % b), пока b не станет равным 0 · Yevklid algoritmiНОК (EKUK): наименьшее общее кратное, равное a * b // EKUB(a, b) · EKUKсокращение дроби: деление числителя и знаменателя на их НОД (EKUB) · kasrni qisqartirish
Объяснение

Нахождение наибольшего общего делителя (НОД, EKUB) двух чисел разложением на простые множители неудобно для компьютера; алгоритм Евклида короток и быстр. Его идея: разделить a на b и взять остаток, затем взять (b, остаток) вместо (a, b); повторять, пока b не станет равным нулю, и в конце a – это НОД. Например, (84, 36) → (36, 12) → (12, 0), значит, НОД = 12. В Python это цикл из двух строк: while b != 0: ⏎     a, b = b, a % b – и обмен, и остаток выполняются в одной строке. Когда НОД найден, сокращение дроби (деление обеих частей на НОД) и нахождение НОК = a * b // EKUB очень просты. Алгоритм всегда останавливается, потому что остаток каждый раз уменьшается и в итоге достигает нуля.

Примеры
Функция НОД: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ print(ekub(84, 36)) ekub(84, 36) = 12.
Сокращение дроби: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ g = ekub(18, 24) ⏎ print(18 // g, 24 // g) дробь 18/24 превращается в 3/4 (НОД = 6). НОК: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ print(12 * 18 // ekub(12, 18)) НОК чисел 12 и 18 равен 36.
Работа в классе

«Цепочка остатков»: пары выбирают два числа, записывают в тетради цепочку (a, b) → (b, a % b) и находят НОД; затем проверяют его с помощью программы.

Упражнения
1
Найдите НОД чисел 48 и 18 (по алгоритму Евклида).
2
Начиная с (84, 36), запишите цепочку: покажите пару (a, b) на каждом шаге.
3
Сокращение дроби: найдите числитель и знаменатель сокращённой дроби 45/60.
4
Почему алгоритм Евклида всегда останавливается?