Практическое занятие: функции и алгоритм Евклида
Находить наибольший общий делитель (НОД) двух чисел разложением на простые множители неудобно для компьютера; алгоритм Евклида же короткий и быстрый. Его идея: a делят на b и берут остаток, затем вместо (a, b) берут (b, остаток); это повторяют, пока b не станет равным нулю, и в конце a равно НОД. Например, (84, 36) → (36, 12) → (12, 0), значит, НОД = 12. В Python это цикл из двух строк (код ниже) – в нём и обмен значений, и остаток выполняются в одной строке. Когда НОД найден, очень легко сократить дробь (разделить обе части на НОД) и найти НОК = a * b // НОД. Алгоритм всегда останавливается, потому что остаток каждый раз уменьшается и в конце концов доходит до нуля.
1while b != 0: 2 a, b = b, a % b
Класс хотел покрыть прямоугольную доску объявлений размером 48 см на 72 см одинаковыми квадратными картинками без промежутков. Наибольшая возможная сторона — наибольший общий делитель чисел 48 и 72, то есть 24 см, поэтому понадобилось 6 картинок.
Математики, программисты и бухгалтеры сокращают дроби, чтобы вычисления были короткими и точными.
Найдите наибольший общий делитель двух чисел, например 36 и 60, на бумаге вычитанием. Используйте его, чтобы сократить дробь.
1def ekub(a, b): 2 while b != 0: 3 a, b = b, a % b 4 return a 5print(ekub(84, 36))
12
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
«Цепочка остатков»: пары выбирают два числа, записывают в тетради цепочку (a, b) → (b, a % b) и находят НОД; затем проверяют его с помощью программы.