Как найти наибольший общий делитель двух чисел python

Как найти наибольший общий делитель двух чисел python

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

def nod(x, y): while (x != y): if x > y: x = x - y else: y = y - x return x x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 1. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

Введите первое число: 30855 Введите второе число: 41514 Наибольший общий делитель 561

Скр. 1. Результат работы программы нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y): while (x != y): x, y = abs(x - y), min(x, y) return x x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 2. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

В программе листинг 2 используются функции abs() и min() вместо операторов if и else в программе листинг 1.

def nod(x, y): while (x % y !=0 and y % x !=0): if x > y: x = x % y else: y = y % x return min(x, y) x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 3. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

def nod(x, y): while (x % y !=0 and y % x !=0): x, y = max(x, y) % min (x, y), min(x, y) return min(x, y) x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 4. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

В программе листинг 4 используются функции max() и min() вместо операторов if и else в программе листинг 3.

def nod(x, y): if (y != 0): return nod(min(x, y), max(x, y) % min (x, y)) else: return x x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 5. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел в программе листинг 5 написана исходя из следующих двух утверждений:

1. Пусть Y = X⋅Q + R, тогда НОД (X, Y) = НОД (X, R), где Q целая часть, а R дробная часть от деления Y/X.
2. НОД(R, 0) = R для любого ненулевого R (так как 0 делится на любое целое число).

def nod(x, y): while y != 0: x, y = y, x % y return x x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 6. Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии.

Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии в программе листинг 6 написана исходя из тех же двух утверждений что и программа листинг 5.

Следует заметить, что в программе листинг 6, так же как и в остальных выше приведённых программах с нахождением остатка от деления большего числа на меньшее используется нахождение остатка от деления большего числа на меньшее. Но в отличие от других приведённых выше программ, выбор большего и меньшего значения аргументов x и y в программе листинг 6 осуществляется за счёт лишней итерации цикла while, вместо использования функций min() и max(). Кроме того, эта лишняя итерация цикла while в программе листинг 6 происходит только в том случае, когда x оказывается меньше y. А это случается только один раз, когда аргументы функции следуют в порядке, с начала меньший, а затем больший.

Сказанное справедливо и для рекурсивной функции нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y): if (y != 0): return nod(y, x % y) else: return x x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 7. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y): return x if (y == 0) else nod(y, x % y) x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 8. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел с использованием тернарного оператора Python.

def nod(x, y): return x if (y == 0) else nod(y, x % y) x = int(input('Введите первое число: ')) y = int(input('Введите второе число: ')) print('Наибольший общий делитель', nod(x, y))

Лист. 8-2. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел одной строкой.

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

© Диордица Александр, гор. Лыткарино, 01.08.2021.

• Вы здесь:
• Главная
• Робототехника
• Алгоритм Евклида. Нахождение НОД

• Быки и коровы на С++
• while Игра кто быстрее 2023
• Функция yield()
• Пуговица и бусина
• Linux или FreeBSD 2023
• Сокеты
• Арифметические и унарные операции
• Коробка 3х3
• Пазлы
• Сапёр 2023
• Пятнадцать 2023
• Что ест уж 2023
• Игровое поле 2023
• Быки и коровы 2023
• Термины и определения
• Программа SOS
• Arduino Blink
• Китайский волчёк
• Головоломка Куб дяди Мити
• Головоломка Ханойская башня
• Головоломка Клёцки
• Головоломка Чайный сервиз
• Головоломка Тетраэдр
• Головоломка Что ест уж
• Головоломка косой Узел
• FreeCAD корпус для Orange Pi 3 LTS
• FreeCad корпус для Raspberry
• Решето Эратосфена
• ESP8266 tty терминал
• Blender отверстия
• Raspberry Pi Pico в Arduino IDE
• MicroPython на Raspberry Pi Pico
• Blink для ESP-C3-13-Kit на MicroPython
• MicroPython MicroREPL
• MicroPython WebREPL
• Драйвер для CH340 в Ubuntu 22.04
• MicroPython для ESP
• MicroPython и GPIO
• Робот на ESP8266 с датчиком HC-SR04
• Задача 001
• Esp8266 и HC-SR04
• ESP8266, драйвер MX1508 и сервопривод
• FORTH на Arduino
• Извлекаем слова из Flash памяти
• Матричная клавиатура
• Игра Flip-Flop
• Lines98 v2
• Логические операции
• Операции сравнения
• Esp8266 управление через web-интерфейс
• Игра 2048
• Битовые операции
• Игра PyNetWalk
• Энкодер
• Игра-головоломка Чайный сервиз v2
• Flip-flop 2x2x5 v2
• Игра Сапёр v3 на Python
• Игра Flip-Flop v3
• Lines98
• Микрофон
• Калькулятор v3
• Где ест уж v3
• Транзистор и фоторезистор.
• Датчик препятствий
• Игровое поле из Button
• Игра Memory
• Датчик инфракрасных импульсов
• Типы C++
• 3-D модель катушки ротора
• ESP32-C3 Wi-Fi точка доступа
• ESP32-C3 FTM
• ESP32-C3 Sigma-Delta модуляция
• Установка Arduino IDE для ESP32-C3
• ESP32-C3 analogReadMilliVolts
• ESP32-C3 Serial.print
• ledcWriteNote для ESP-C3-Kit
• Плата ESP-C3-32S Kit
• ШИМ в ESP-C3 Kit
• Программа Blink для ESP-C3 Kit
• Подключение ESP-C3-Kit к Arduino IDE
• Плата ESP-C3-13 Kit
• Калькулятор с tkinter
• Драйвер моторов MX1508
• Калькулятор на Arduino
• Raspberry Pi Pico Python SDK
• Raspberry Pi Pico C/C++ SDK
• Программирование на MMBASIC
• PicoMiteVGA
• Сервопривод и Ардуино
• Arduino машина с ИК управлением
• Двигатель постоянного тока
• ИК пульт ДУ
• Ультразвуковой дальномер HC-SR04
• АЦП и ШИМ в Arduino
• Крестики нолики v2.0
• Программа для музыкальной шкатулки
• Ханойские башни, игра
• Flip-Flop 4×4 и ООП
• AT90S2013 с внешним генератором
• Игра Кто быстрее
• Игра головоломка Peg
• Поход в пустыню
• Оригинальная игра Сапёр
• Программирование ATtiny861
• Программирование AT90S2013
• StringVar или ООП
• Клеточный автомат Конвея
• Flip-Flop 4×4 .
• ООП, after() функция задержки в tkinter
• Программирование AtTiny 13, 45, 85
• Игра-головоломка Где ест уж
• Игра-головоломка Чайный сервиз
• Пишем игру Flip-Flop v2
• Игра Быки и коровы на Python v2
• Крестики нолики
• Python сортировка
• Игра Красный или Синий?
• Индикатор 788BS
• Python Факториал
• Генератор псевдослучайных чисел
• Датчик температуры в ATtiny88
• Serial порт в ATtiny88
• Пишем библиотеку для MAX7219 и LED матрицы
• MAX7219 и Arduino
• Прерывания PCINT в Arduino
• Функция sleep() в Arduino для ATtiny88
• ATtiny88 datasheet на русском
• Фьюзы ATtiny88
• Arduino Fading and Blink
• Алгоритм Евклида. Нахождение НОД
• Python Числа Фибоначчи
• Python Tkinter игра Пикассо и Модильяни
• Ищем программатор для STM 32F030F4P6
• Python Tkinter игра Раскраска
• Пишем игру Быки и Коровы на Python
• Головоломка Ханойские башни на Python
• Головоломка Ханойские башни на Си
• Пишем игру Сапёр на Python
• Raspberry Pi Pico fading.py
• LCD МТ-16S2H и LiquidCrystal_74HC595
• EasyEDA для инженеров-электронщиков
• LCD МТ-16S2H и LiquidCrystalRus
• Raspberry Pi Pico и MicroPython
• Пишем игру пятнашки на Python
• Пишем игру на Python
• ESP8266 версии плат
• Регистр К155ИР13
• Linux или FreeBSD
• Триггеры
• Счетчик импульсов на 7493
• Счетчик импульсов на D-триггерах
• Цифровые индикаторы с общим катодом
• ATtiny88 программируем в Arduino IDE
• Конденсатор в кружке Робототехника
• Генератор на 555-м таймере
• Генератор НЧ на LM358
• Tkinter виджеты
• Pydoc в Python
• LM358 управление голосом
• Несимметричный мультивибратор
• QX5252F схема включения
• DC-DC uk преобразователь на QX5252
• DC-DC преобразователь на QX5252
• Python с Pygame обработка столкновений
• Логика в Python
• Сова на телевизор
• Транзисторы p-n-p и n-p-n
• IDLE
• Thonny установка и настройка
• Timer/Counter1 ATmega328
• Arduino IDE
• ATMEGA8
• Прерывания по таймерам в Arduino
• DC-DC преобразователь
• LED лампа светодиодная
• MOSFET
• Концепция музыкальной программы для Arduino
• Стробоскоп на 555-м таймере
• ШИМ на 555-м таймере
• ШИМ управление мощностью нагрузки
• Вентилятор для CPU и Arduino
• ATmega328P
• Храним константы в Flash-памяти программ
• Храним константы в EEPROM
• Параметры по умолчанию
• Цикл for в Arduino
• Драйвер MAX7219 и светодиодная матрица 8х8
• WS2811 и RGB светодиод
• Assembler в Arduino
• Python Gtk игра Раскраска
• LGT8F328P в Arduino IDE
• Адрес i2c
• Музыкальная шкатулка
• LCD 1602 i2c и Arduino
• Корпус VESA для Orange Pi PC 2
• Blink для адресуемых RGB светодиодов
• ESP8266-01 Web-сервер
• ESP8266 прошивка AT-espressif
• Edragon, ESP firmware
• Esptool
• ESP8266 в Arduino IDE
• ESP8266-01 подключение USB-UART
• ESP8266-01 AT интерпретатор
• CuteCom монитор порта
• ESP8266-01 подключение
• SSD1306 IIC print()
• ATMega328 в Arduino без кварца
• Фьюзы в Arduino UNO
• Программирование Arduino Pro Mini
• L7805 стабилизатор напряжения
• MLX90614 — ИК термометр
• Датчик ИК импульсов
• Arduino-Hava Nagila
• Arduino-Финская полька
• Arduino-Гимн РФ
• Arduino-Григ В пещере Горного Короля
• heaptrack профилировщик памяти
• Консольная программа на Visual J#
• Консольная программа на C#
• Консольная программа на Visual Basic.NET
• Blender на русском
• Arduino Digispark ATTiny85
• cairo.Context object Деформации
• cairo.Context object Фигуры Лиссажу
• cairo.Context object Движение по криволинейной траектории
• cairo.Context object Пинг-понг по стенкам
• cairo.Context object Загружаем картинку
• cairo.Context object Трансформация прямоугольных координат
• cairo.Context object Штриховые линии
• cairo.Context object Шар с радиальной заливкой
• cairo.Context object Градиентная заливка
• cairo.Context object Сдвигаем и вращаем начало координат
• cairo.Context object Начало координат
• cairo.Context object Сглаживание контура изображения или шрифта
• cairo.Context object Углы соединения линий
• cairo.Context object Рисуем линии
• Gtk Drawin Area и GObject
• Gtk Drawin Area и PangoCairo
• Python Gtk окно с текстом
• Python Gtk игра Flip-Flop
• Python Gtk Крестики — нолики
• Anjuta Gtk Python Кнопка
• Visual Studio Code редактор
• Vala язык программирования
• Anjuta Gtk Python
• Glade Gtk Python сигналы
• Glade Gtk Python
• Python графическая библиотека Turtle
• Python графическая библиотека GTK
• Python графическая библиотека Tkinter
• Инкубатор
• Пример программы на Python с библиотекой Pygame
• Создание игр на Python с Pygame
• Классическая игра Жизнь
• Игра Жизнь на дисплее SSD1306 и Arduino
• SSD1306 Display
• Импульсный регулятор мощности на Ардуино
• Оператор switch case. Электронная игра на Arduino.
• Игра инверсия
• Android пишем программу на C++
• Цикл while. Алгоритм Евклида.
• Geany пишем программу на C++
• Как скомпилировать cpp под Linux
• Схема преобразователя напряжения на транзисторе
• Схема фонарика с 2-мя батарейками

• Author Login
• Карта сайта

© 2023 Системный интегратор

Наибольший общий делитель для списка натуральных чисел

В модуле math есть функция math.gcd(a, b), возвращающая наибольший общий делитель (НОД) двух чисел. При помощи functools.reduce вычислите и напечатайте наибольший общий делитель для списка натуральных чисел, поступающих в стандартный поток ввода.
Не забудьте подключить модуль math командой import math.
Примечание: В старых версиях Python (до 3.5) функция gcd находилась в модуле fractions (а в настоящий момент она находится в обоих модулях одновременно). Если вы работаете со старой версией Python, то вам необходимо использовать fractions.gcd.

Формат ввода
36
12
144
18

Формат вывода
6

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Найдите наибольший общий делитель двух натуральных чисел
Найдите наибольший общий делитель двух натуральных чисел. Целые числа могут быть большими, поэтому.

Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел
Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел. Пример: .

Наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) двух натуральных чисел
Здравствуйте, не могу решить эти две задачи в питоне, помогите пожалуйста, необходимо: Составить.

Наибольший общий делитель четырех чисел
Здравствуйте. Я новичок по программированию на питоне.Задание следующее: написать функцию.

Просто Лис

5321 / 3335 / 1021
Регистрация: 17.05.2012
Сообщений: 9,768
Записей в блоге: 9
И? В чём сложности?
Регистрация: 25.03.2018
Сообщений: 91
Рыжий Лис, не понял как это сделать
Просто Лис

5321 / 3335 / 1021
Регистрация: 17.05.2012
Сообщений: 9,768
Записей в блоге: 9
functools.reduce не знаете как воспользоваться?
Регистрация: 25.03.2018
Сообщений: 91
Рыжий Лис, знал бы — не написал бы сюда
Просто Лис

5321 / 3335 / 1021
Регистрация: 17.05.2012
Сообщений: 9,768
Записей в блоге: 9

1 2 3 4 5 6 7

#!/usr/bin/env python3 try: from math import gcd except ImportError: from fractions import gcd from functools import reduce print(reduce(gcd, [36, 12, 144, 18]))

Регистрация: 25.03.2018
Сообщений: 91
Рыжий Лис, Answers do not match: out = 6, corr = 1
513 / 145 / 28
Регистрация: 18.04.2015
Сообщений: 1,872
Записей в блоге: 15

Pavlin235, вот вроде решение

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)

Добавлено через 6 минут
Как можно еще больше сократить это решение?

5416 / 3840 / 1214
Регистрация: 28.10.2013
Сообщений: 9,554
Записей в блоге: 1

Сообщение от IRIP

Как можно еще больше сократить это решение?

1 2 3 4

def gcd(x, y): while y: x, y = y, x % y return x

Но ТС нужна была не кастомная функция НОД, а функциональный подход с использованием reduce для списка.

513 / 145 / 28
Регистрация: 18.04.2015
Сообщений: 1,872
Записей в блоге: 15

Сообщение от Garry Galler

Но ТС нужна была не кастомная функция НОД, а функциональный подход с использованием reduce для списка

вроде мы с ним по одной программе занимаемся.

конкретно вот этот код как можно сократить, чтобы он сохранял свою работоспособность?

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)

Как найти НОД двух чисел в Python – 4 способа

НОД – это математический термин, обозначающий наибольший общий делитель, который может идеально разделить два числа. НОД также известен как наибольший общий фактор(HCF).

Например, HCF / GCD двух чисел 54 и 24 равен 6. Поскольку 6 – это наибольший общий делитель, который полностью делит 54 и 24.

Разберемся как найти НОД двух чисел в Python.

НОД с использованием функции gcd()

gcd() в python – это встроенная функция, предлагаемая математическим модулем для поиска наибольшего общего делителя двух чисел.

gcd(a, b)

Где a и b – два целых числа, которые передаются в качестве аргумента функции gcd().

Давайте создадим программу для печати НОД двух чисел, используя встроенную функцию math.gcd() в python.

# create a program to print the gcd of two number in python using the math.gcd() function. import math print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number print(" GCD of two number 0 and 48 is ", math.gcd(0, 48)) a = 60 # assign the number to variable a b = 48 # assign the number to variable b print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function. print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18)) print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48))

В приведенном выше примере функция math.gcd() генерирует НОД двух заданных чисел. В функции gcd() a и b передаются в качестве аргумента, который возвращает наибольший общий делитель двух целых чисел, полностью разделяя числа.

НОД с использованием рекурсии

Рекурсия – это функция, потребляющая память, определенная в Python, которая вызывает себя через самореферентное выражение. Это означает, что функция будет постоянно вызывать и повторять себя до тех пор, пока не будет выполнено определенное условие для возврата наибольшего общего делителя числа.

Псевдокод алгоритма

Шаг 1: Возьмите два входа, x и y, от пользователя.

Шаг 2: Передайте входной номер в качестве аргумента рекурсивной функции.

Шаг 3: Если второе число равно нулю(0), возвращается первое число.

Шаг 4: В противном случае он рекурсивно вызывает функцию со вторым числом в качестве аргумента, пока не получит остаток, который делит второе число на первое число.

Шаг 5: Вызовите или назначьте gcd_fun() переменной.

Шаг 6: Отобразите НОД двух чисел.

Шаг 7: Выйдите из программы.

Разберемся с программой для нахождения НОД двух чисел с помощью рекурсии.

# write a program to understand the GCD of two number in python using the recursion. def gcd_fun(x, y): if(y == 0): # it divide every number return x # return x else: return gcd_fun(y, x % y) x =int(input("Enter the first number: ")) # take first no. y =int(input("Enter the second number: ")) # take second no. num = gcd_fun(x, y) # call the gcd_fun() to find the result print("GCD of two number is: ") print(num) # call num

Нахождение НОД с помощью цикла

Давайте создадим программу для нахождения НОД двух чисел в Python с помощью циклов.

def GCD_Loop( a, b): if a > b: # define the if condition temp = b else: temp = a for i in range(1, temp + 1): if(( a % i == 0) and(b % i == 0 )): gcd = i return gcd x = int(input(" Enter the first number: ") ) # take first no. y =int(input(" Enter the second number: ")) # take second no. num = GCD_Loop(x, y) # call the gcd_fun() to find the result print("GCD of two number is: ") print(num) # call num

Как мы видим в приведенной выше программе, мы берем два значения в качестве входных и передаем эти числа в функцию GCD_Loop(), чтобы вернуть GCD.

Алгоритм Евклида

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

Например, предположим, что мы хотим вычислить HCF двух чисел, 60 и 48. Затем мы делим 60 на 48; он возвращает остаток 12. Теперь мы снова делим число 24 на 12, а затем он возвращает остаток 0. Таким образом, мы получаем HCF равным 12.

Псевдокод алгоритма Евклида

Шаг 1: Есть два целых числа, например a и b.

Шаг 2: Если a = 0, то НОД(a, b) равен b.

Шаг 3: Если b = 0, НОД(a, b) равен a.

Шаг 4: Найти mod b.

Шаг 5: Предположим, что a = b и b = R.

Шаг 6: Повторяйте шаги 4 и 3, пока mod b не станет равным или большим 0.

Шаг 7: GCD = b и затем распечатайте результат.

Шаг 8: Остановите программу.

Найдем HCF или GCD двух чисел, используя алгоритм Евклида в python.

# Create a program to find the GCD of two number in python using the Euclid's Algorithm. def find_hcf(a,b): while(b): a, a = b, a % b return a a = int(input(" Enter the first number: ") ) # take first no. b = int(input(" Enter the second number: ")) # take second no. num = find_hcf(a, b) # call the find_hcf() to get the result print(" The HCF of two number a and b is ") print(num) # call num

Нахождение наибольшего общего делителя (НОД) при помощи рекурсии

Программа принимает на вход два числа и находит наибольший общий делитель (НОД) с использованием рекурсии.

Решение задачи

1. Принимаются два числа, которые сохраняются в отдельные переменные.
2. Передаем оба числа в рекурсивную функцию в качестве аргумента.
3. В качестве базового условия рекурсии принимаем равенство нулю второго числа (второго аргумента функции). В этом случае результатом работы функции является первое число (первый аргумент функции).
4. В противном случае снова рекурсивно вызываем эту функцию и в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции, а в качестве второго — остаток от деления первого аргумента на второй аргумент.
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат на экран.
7. Конец.

Исходный код

Ниже дан исходный код, который осуществляет нахождение наибольшего общего делителя (НОД) с использованием рекурсии. Результаты работы программы также даны ниже.

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)

Объяснение работы программы

1. Пользователь вводит два числа и они записываются в переменные a и b .
2. Затем эти два числа передаются в качестве аргументов в рекурсивную функцию gcd() .
3. В качестве базового условия рекурсии принимаем равенство 0 второго аргумента функции: b == 0 . В этом случае результатом работы функции будет первый аргумент a .
4. В противном случае снова рекурсивно вызываем нашу функцию следующим образом: gcd(b, a % b) . То есть, в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции ( b ), а в качестве второго —остаток от деления a на b .
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат работы функции на экран.

Результаты работы программы

Пример 1: Введите первое число:5 Введите второе число:15 НОД: 5 Пример 2: Введите первое число:30 Введите второе число:12 НОД: 6