Цель: научиться выделять цифры из числа и выполнять операции над ними, используя основные алгоритмические конструкции.
Существует несколько способов нахождения НОД. На уроках математики вы раскладывали каждое число на простые множители, выбирали общие множители и перемножали их. Для программной реализации удобнее другой способ — алгоритм Евклида, который не требует разложения чисел на множители.
| Алгоритм Евклида — алгоритм для нахождения НОД двух целых чисел. Он назван в честь древнегреческого математика Евклида (III в. до н. э.), который впервые описал его в книгах «Начала». Это один из старейших численных алгоритмов, используемых в наше время. |
Идея алгоритма Евклида в форме вычитания состоит в следующем:
1. Из большего числа вычитаем меньшее.
2. Если получается 0, то числа равны друг другу, и значение НОД равно любому из этих чисел.
3. Если результат вычитания не равен 0, то большее число заменяем на разность большего и меньшего.
4. Переходим к пункту 1.
Схема работы алгоритма показана на рисунке. Цикл продолжается, пока числа не станут равными.

Пример 1. Ира и Игорь коллекционируют значки: у Иры в коллекции a значков, а у Игоря — b. Ребята решили разделить все свои значки между друзьями без остатка. Какое наибольшее количество общих друзей может быть у Иры и Игоря? Например, при a = 42 и b = 24 значки можно разделить между 1, 2, 3 или 6 общими друзьями; наибольшее количество — 6.
Рассуждение. Поскольку значки нужно делить без остатка, ответом может быть только общий делитель чисел a и b. Наибольшему количеству друзей соответствует наибольший общий делитель. Значит, ответ на задачу — НОД (a; b), вычислим его по алгоритму Евклида.
Этапы выполнения задания:
I. Исходные данные: a и b — количество значков у Иры и у Игоря.
II. Результат: наибольшее количество общих друзей.
III. Алгоритм: описываем функцию nod(a, b); пока a ≠ b, сравниваем числа и заменяем большее разностью; функция возвращает a (числа в этот момент равны).IV. Описание переменных: все переменные имеют тип int
def nod(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
a = int(input("у Иры a = "))
b = int(input("У Игоря b = "))
c = nod(a, b)
print("всего друзей =", c)
Результат работы программы:

Готовые функции gcd() и lcm()
В библиотеке math языка Python есть функция gcd(), которая вычисляет наибольший общий делитель, и функция lcm(), вычисляющая наименьшее общее кратное (НОК). Обе функции могут иметь произвольное количество параметров, поэтому НОД и НОК трёх и более чисел находятся без вспомогательных вызовов.
Пример 2. Найти НОК и НОД трех чисел.
from math import *
print("три числа через пробел")
x, y, z = map(int, input().split())
d = gcd(x, y, z) # НОД
f = lcm(x, y, z) # НОК
print("НОД =", d)
print("НОК =", f)
Обратите внимание: команда map(int, input().split()) читает одну строку и преобразует каждое записанное в ней через пробел число в целое значение. Так в одной команде можно ввести сразу несколько чисел

Задания по теме урока
Задание 1. Используя пример 2, найти НОК и НОД четырёх чисел.
Задание 2. С клавиатуры вводится числитель и знаменатель дроби. Необходимо сократить дробь.
Подсказка: Чтобы сократить дробь, нужно найти наибольшее число, на которое делятся и числитель, и знаменатель — это и есть НОД.
Задание 3. Две правильные дроби заданы своими числителями и знаменателями. Найти сумму дробей. Дробь можно не сокращать.
Подсказка:
- Сначала приводим дроби к наименьшему общему знаменателю (НОК).
- Складываем получившиеся числители.
- Сокращаем результат с помощью НОД.
- Делим числитель на знаменатель нацело (
//), чтобы получить целую часть, а остаток от деления (%) становится новым числителем дробной части.
Дополнительное задание. В задании 3 вывести ответ в виде смешанной дроби.

Домашнее задание
§ 7.7 учебного пособия, ответить на вопросы
