Главная » Языки программирования

Алгоритм евклида вычитанием питон

Алгоритм евклида вычитанием питон

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

Читайте также:  Python inheritance init super

В программе листинг 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.

  • Вы здесь:
  • Главная
  • Робототехника
  • Алгоритм Евклида. Нахождение НОД
  • Игра Сапёр 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 in в 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 Системный интегратор

Источник

Оцените статью
© 2024 Программирование