РекламаЗдесь может быть ваш брендВаш бренд здесьНа каждой странице Darslab · ученики, родители и учителяinfo@darslab.comУзнать ценыЦеныinfo@darslab.com
☰ Содержание · Информатика

Локальные и глобальные переменные, функция НОД (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
Объяснение

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

Python
1while b != 0:
2    a, b = b, a % b
💡 Где это пригодится?
Пример из жизни

Класс хотел покрыть прямоугольную доску объявлений размером 48 см на 72 см одинаковыми квадратными картинками без промежутков. Наибольшая возможная сторона — наибольший общий делитель чисел 48 и 72, то есть 24 см, поэтому понадобилось 6 картинок.

Кто это использует

Математики, программисты и бухгалтеры сокращают дроби, чтобы вычисления были короткими и точными.

Попробуйте сегодня

Найдите наибольший общий делитель двух чисел, например 36 и 60, на бумаге вычитанием. Используйте его, чтобы сократить дробь.

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

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

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