Статья Автор: Корельская Елена Юрьевна

Теория

Сегодня на уроке рассмотрим применение цикла 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)

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

Печать