Урок 12. Использование основных алгоритмических конструкций и вспомогательных алгоритмов для практических задач.

Цель: научиться выделять цифры из числа и выполнять операции над ними, используя основные алгоритмические конструкции.


Существует несколько способов нахождения НОД. На уроках математики вы раскладывали каждое число на простые множители, выбирали общие множители и перемножали их. Для программной реализации удобнее другой способ — алгоритм Евклида, который не требует разложения чисел на множители.

Алгоритм Евклида — алгоритм для нахождения НОД двух целых чисел. Он назван в честь древнегреческого математика Евклида (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. Две правильные дроби заданы своими числителями и знаменателями. Найти сумму дробей. Дробь можно не сокращать.

Подсказка:

  1. Сначала приводим дроби к наименьшему общему знаменателю (НОК).
  2. Складываем получившиеся числители.
  3. Сокращаем результат с помощью НОД.
  4. Делим числитель на знаменатель нацело (//), чтобы получить целую часть, а остаток от деления (%) становится новым числителем дробной части.

Дополнительное задание. В задании 3 вывести ответ в виде смешанной дроби.


Это изображение имеет пустой атрибут alt; его имя файла - hw-e1653285769766.png

Домашнее задание

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

Добавить комментарий