Нахождение наибольшего общего делителя (НОД) при помощи рекурсии
Программа принимает на вход два числа и находит наибольший общий делитель (НОД) с использованием рекурсии.
Решение задачи
- Принимаются два числа, которые сохраняются в отдельные переменные.
- Передаем оба числа в рекурсивную функцию в качестве аргумента.
- В качестве базового условия рекурсии принимаем равенство нулю второго числа (второго аргумента функции). В этом случае результатом работы функции является первое число (первый аргумент функции).
- В противном случае снова рекурсивно вызываем эту функцию и в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции, а в качестве второго — остаток от деления первого аргумента на второй аргумент.
- Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
- Выводим результат на экран.
- Конец.
Исходный код
Ниже дан исходный код, который осуществляет нахождение наибольшего общего делителя (НОД) с использованием рекурсии. Результаты работы программы также даны ниже.
def gcd(a, b): if (b == 0): return a else: return gcd(b, a % b) a = int(input("Введите первое число:")) b = int(input("Введите второе число:")) GCD = gcd(a, b) print("НОД: ") print(GCD)
Объяснение работы программы
- Пользователь вводит два числа и они записываются в переменные a и b .
- Затем эти два числа передаются в качестве аргументов в рекурсивную функцию gcd() .
- В качестве базового условия рекурсии принимаем равенство 0 второго аргумента функции: b == 0 . В этом случае результатом работы функции будет первый аргумент a .
- В противном случае снова рекурсивно вызываем нашу функцию следующим образом: gcd(b, a % b) . То есть, в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции ( b ), а в качестве второго —остаток от деления a на b .
- Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
- Выводим результат работы функции на экран.
Результаты работы программы
Пример 1: Введите первое число:5 Введите второе число:15 НОД: 5 Пример 2: Введите первое число:30 Введите второе число:12 НОД: 6
Алгоритм Евклида — нахождение наибольшего общего делителя
Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.
Решение задачи на языке программирования Python
Алгоритм нахождения НОД делением
- Большее число делим на меньшее.
- Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
- Если есть остаток, то большее число заменяем на остаток от деления.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6
a = int(input()) b = int(input()) while a != 0 and b != 0: if a > b: a = a % b else: b = b % a print(a + b)
В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.
Если условием завершения цикла является равенство хотя бы одной из переменных нулю ( a == 0 or b == 0 ), то условием продолжения его работы является обратное этому условие — обе переменные должны иметь отличные от нуля значения ( a != 0 and b != 0 ).
Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs ( a ) > abs ( b ) : . Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.
Алгоритм нахождения НОД вычитанием
- Из большего числа вычитаем меньшее.
- Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
- Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
- Переходим к пункту 1.
Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6
a = int(input()) b = int(input()) while a != b: if a > b: a = a - b else: b = b - a print(a)
Функция, вычисляющая НОД
def gcd(m, n): while m != n: if m > n: m = m - n else: n = n - m return n a = int(input()) b = int(input()) print(gcd(a, b))
Функция gcd модуля math
В модуле math языка программирования Python есть функция gcd , вычисляющая наибольший общий делитель двух чисел.
>>> import math >>> math.gcd(30, 18) 6
X Скрыть Наверх
Решение задач на Python
Уровень b напишите функцию которая находит наибольший общий делитель двух натуральных чисел
«. В жизни я встречал друзей и врагов.В жизни много всего перевидал.Солнце тело мое жгло, ветер волосы трепал,но я смысла жизни так и не узнал. »
(c) Юрий Клинских aka «Хой»
Форумчанин
Регистрация: 05.04.2010
Сообщений: 410
Сообщение от _-Re@l-_
ой-ой-ой.
Вот так:
Function NOD(M,N:Integer):Integer; Begin While M<>N Do Begin If M>N Then M:=M-N Else M:=N-M; End; Nod:=M; End;И всё, больше ничего не надо,это вся функция!
ты ее специально написал, чтобы я запустил ее и прога зависла.
ICQ: 593-013-807
| Don Karleone |
| Посмотреть профиль |
| Найти ещё сообщения от Don Karleone |
Регистрация: 10.04.2010
Сообщений: 2,665
Оооо. Я никогда не был силен в рекурсии.
| ты ее специально написал, чтобы я запустил ее и прога зависла. |
Почему. У меня ничего не зависает и нормально работает.
Форумчанин
Регистрация: 05.04.2010
Сообщений: 410
Сообщение от _-Re@l-_
Оооо. Я никогда не был силен в рекурсии.
Почему. У меня ничего не зависает и нормально работает.
тогда делаем так NOD(64,48).
ICQ: 593-013-807
| Don Karleone |
| Посмотреть профиль |
| Найти ещё сообщения от Don Karleone |
Регистрация: 10.04.2010
Сообщений: 2,665
И что? нод 64 и 48 16, что вам не нравится?
Форумчанин
Регистрация: 05.04.2010
Сообщений: 410
Сообщение от _-Re@l-_
И что? нод 64 и 48 16, что вам не нравится?
хз. скопировал код, запустил, зацикливается.
ICQ: 593-013-807
| Don Karleone |
| Посмотреть профиль |
| Найти ещё сообщения от Don Karleone |
| Страница 1 из 2 | 1 | 2 | Следующая > |
| Похожие темы | ||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| [C++ Файли]Определить наибольший общий делитель трех натуральных чисел. | basav1k | Фриланс | 6 | 06.06.2010 18:24 |
| [C++ Файли]Определить наибольший общий делитель трех натуральных чисел. | basav1k | Помощь студентам | 1 | 27.05.2010 18:00 |
| Вычислить наибольший общий делитель двух натуральных чисел А и В | SsIDit | Помощь студентам | 1 | 09.05.2010 11:54 |
| функция gcd, которая возвращает наибольший общий делитель двух целых чисел | Jereme | Общие вопросы C/C++ | 2 | 21.01.2010 01:49 |
| Определить из наибольший общий делитель, используя функцию нахождения общего делителя. | Igomax | Помощь студентам | 6 | 23.05.2009 19:41 |
Наибольший общий делитель двух чисел
Вычислите наибольший общий делитель чисел A и B согласно алгоритму Евклида
Задание на рекурсивный алгоритме: Вычислите наибольший общий делитель чисел A и B согласно.
Наибольший общий делитель
Написать функцию, которая вычисляет наибольший общий делитель двух целых чисел.
Наибольший общий делитель прямоугольников
Будем говорить, что прямоугольник PP является делителем прямоугольника QQ, если прямоугольник QQ.
Сократить дробь, используя наибольший общий делитель
Даны два натуральных числа a и b, обозначающие соответственно числитель и знаменатель дроби.
Найдите наибольший общий делитель двух натуральных чисел
Найдите наибольший общий делитель двух натуральных чисел. Целые числа могут быть большими, поэтому.
1354 / 651 / 207
Регистрация: 23.03.2014
Сообщений: 3,057
Сообщение было отмечено mik-a-el как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
# ввод целых чисел a = int(input()) b = int(input()) # Пока какое-нибудь из двух числе не будет равно 0, while a != 0 and b != 0: # сравнивать их между собой. # Если первое число больше второго, if a > b: # то находить остаток от деления его на второе число # и присваивать его первой переменной a = a % b # Иначе (когда второе число больше первого) else: # присваивать второй переменной остаток от деления # нацело второго числа на первое b = b % a # Одно из чисел содержит 0, а другое - НОД, но какое - неизвестно. # Проще их сложить, чем писать конструкцию if-else gcd = a + b print(gcd)