Курсы

Программирование 8 класс

Урок 14. Алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел

Модуль: Урок 14. Алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел

1. Теория

Сегодня на уроке рассмотрим применение цикла while для нахождения наибольшего общего делителя двух чисел. Наибольший общий делитель (НОД) двух целых чисел — это наибольшее число, на которое можно разделить оба этих числа.
В курсе математики вы научились находить НОД при помощи разложения на множители. Есть другой метод нахождения НОД - алгоритм Евклида. Существуют два способа нахождения НОД реализации алгоритма Евклида: вычитание и деление. Рассмотрим оба этих варианта.
Алгоритм Евклида с использованием вычитания:

Если числа равны, то любое из них является наибольшим общим делителем.
Если числа не равны, выбираем большее число и вычитаем из него меньшее.
Возвращаемся к шагу 1, но теперь работаем с меньшим числом и результатом вычитания.

Пример, a = 44, b = 60

Итерация	Условие	a	b
		44	60
1	44 != 60 (истина)	44	60-44 = 16
2	44 != 16 (истина)	44-16 = 28	16
3	28 != 16 (истина)	28-16=12	16
4	12 != 16 (истина)	12	16-12=4
5	12 != 4 (истина)	12-4=8	4
6	8 != 4 (истина)	8-4=4	4
	4 != 4 (ложь)	Ответ: 4

Реализация алгоритма Евклида с использованием вычитания на Python:

a = int(input())
b = int(input())
while a != b:
    if a > b:
        a -= b
    else:
        b -= a
print(b)

Алгоритм Евклида, основанный на делении, является более эффективным методом нахождения наибольшего общего делителя, чем алгоритм, использующий вычитание.

Большее число делим на меньшее.
Если остаток от деления равен нулю, то ответ – меньшее число
Если остаток не равен нулю, то большее число заменяем на остаток от деления.
Возвращаемся к шагу 1.

Пример, a = 44, b = 60

Итерация	Условие	a	b
		44	60
1	60 % 44 != 0 (истина)	44	60 % 44 = 16
2	44 % 16 != 0 (истина)	44 % 16 = 12	16
3	16 % 12 != 0 (истина)	12	16 % 12 = 4
	12 % 4 != 0 (ложь)	Ответ: 4

a = int(input())
b = int(input())
while a!=b:
  if a > b:
    a -= b
  else:
    b =-a
print(b)

time 1000 ms
memory 256 Mb

Комментарий учителя

Обсуждения (0)

Чтобы оставить комментарий нужна авторизация

Решения (0)

Решения:

Нет доступных решений