Алгоритм Евклида – это алгоритм для поиска наибольшего общего делителя двух чисел. Алгоритм впервые описан древнегреческим математиком Евклидом.
Наибольший общий делитель (НОД) – это наибольшее число, на которое делятся заданные числа без остатка.
Алгоритм основан на том, что наибольший общий делитель пары чисел, не меняется, если из большего числа вычесть меньшее. Если повторять операцию вычитания, то в конце приходим к тому, что одно из чисел становится равным нулю, а второе является НОД.
Рекурсивная реализация поиска наибольшего общего делителя
Напишем два вспомогательных метода, которые возвращают минимальное и максимальное из двух чисел:
static int Min(int x, int y) < return x < y ? x : y; >static int Max(int x, int y) < return x > y ? x : y; >
Нахождение НОД для двух чисел c использованием вычитания
При каждом рекурсивном вызове вычитаем из максимального числа минимальное, повторяя рекурсивные вызовы до тех пор, пока первый аргумент не будет равен нулю:
Наибольший общий делитель. 5 класс.
static int GCD(int a, int b) < if (a == 0) < return b; > else < var min = Min(a, b); var max = Max(a, b); //вызываем метод с новыми аргументами return GCD(max — min, min); > >
Использование оператора остатка от деления % для вычисления НОД
Для уменьшения количества рекурсивных вызовов, при вычислении, можно воспользоваться оператором остатка от деления и вместо разницы, передавать в метод остаток от деления максимального числа на минимальное. Чтобы ускорить алгоритм, достаточно изменить знак в строке возврата предыдущего метода с “-” на “%”:
return GCD(max % min, min);
Использование остатка очень ускоряет работу алгоритма поиска НОД. К примеру для пары чисел 1013 и 65 с использованием вычитания метод вызывается 27 раз, а с остатком от деления всего 7.
Вычисление НОД в циклах
Циклическое вычисление наибольшего общего делителя с вычитанием
static int GCD(int a, int b) < if (a == 0) < return b; > else < while (b != 0) < if (a > b) < a -= b; >else < b -= a; >> return a; > >
Циклический поиск наибольшего общего делителя с остатком от деления
static int GCD(int a, int b) < while (b != 0) < var temp = b; b = a % b; a = temp; > return a; >
Программа для поиска НОД чисел
Напишем программу, в которой будем использовать один из методов рассмотренных выше:
using System; class Program < static int GCD(int a, int b) < while (b != 0) < var t = b; b = a % b; a = t; > return a; > static void Main(string[] args) < Console.WriteLine(«Алгоритм Евклида»); Console.Write(«A hljs-keyword»>var a = Convert.ToInt32(Console.ReadLine()); Console.Write(«B hljs-keyword»>var b = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(«Наибольший общий делитель чисел и равен «, a, b, GCD(a, b)); Console.ReadLine(); > >
Результат работы программы:
Алгоритмы. Наибольший общий делитель. Реализация на Python и Java.
Для чисел 36 и 60 программа возвращает значение 12.
Наибольший общий делитель трех чисел
Для получения НОД для трех чисел и более чисел необходимо вызывать метод следующим образом:
var n1 = GCD(GCD(15, 30), 75); //для трех параметров результат 15 var n2 = GCD(GCD(16, 36), GCD(585, 360)); //для четырех чисел результат 1
В первом примере сначала вычисляется НОД(15, 30) = 15, потом результат вычислений передается в качестве аргумента и вычисляется НОД(15, 75) = 15. Во втором примере вычисляются НОД(16, 36) = 4 и НОД(585, 360) = 45, а результаты передаются в метод НОД(4, 45) = 1.
Источник: programm.top
VladHub18 / FunctionsTask 8.py
Напишите функцию, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| a = int ( input ()) |
| b = int ( input ()) |
| def NOD ( a , b ): |
| while a != b : |
| if a > b : |
| a = a — b |
| else : |
| b = b — a |
| return a |
| print ( NOD ( a , b )) |
| def NOK ( a , b ): |
| a = a * b // NOD ( a , b ) |
| return a |
| print ( NOK ( a , b )) |
snz-git commented Nov 20, 2022
А если нужно отделить эти две программы, то есть отдельно нахождение НОД и НОК.
Пытаюсь переписать код для нахождения НОК, но не получается. Вариант с вызовом функции НОДа отпадает.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Footer
You can’t perform that action at this time.
Источник: gist.github.com
Вычисление наибольших общих делителей
Найти наибольшие общие делители (НОД) для множества пар чисел.
Пусть пользователь будет вводить пары чисел, а на экран будут выводиться наибольшие общие делители этих чисел. В таком случае программу можно организовать следующим образом.
В основной ветке программы будет цикл, в теле которого будут
- запрашиваться два числа,
- вызываться функция для вычисления наибольшего общего делителя,
- возвращаемый функцией результат выводиться на экран.
Условие прекращения работы цикла основной программы — ввод пользователем двух нулей.
НОД будет вычисляться в функции, которая будет получать два числа, а возвращать их НОД. Алгоритм нахождения НОД может быть следующим. Пока оба числа не равны нулю, находить остаток от деления большего числа на меньшее и присваивать его переменной, где хранилось большее число. После цикла сложить значения обоих переменных, — это и есть НОД.
На самом деле НОД содержится только в одной переменной, а вторая имеет нулевое значение (это условие окончания цикла). Однако нам неизвестно какая из двух содержит 0, поэтому проще их сложить, чем это выяснять.
Почему НОД можно определить таким способом (следует знать, что он не единственный)? Представим, что у нас два числа: 18 и 12. Остаток от деления 18 на 12 будет 6. Далее имеется два числа 12 и 6. Остаток от деления первого на второе равен 0. Он записывается на место числа 12. Получаем 0 и 6. Таким образом 12 делится нацело на 6, а вот как пояснить логически, что и 18 на него должно делиться?
Pascal
var a, b: word;
function gcd(c, d: word): word;
begin
while (c <> 0) and (d <> 0) do
if c > d then
c := c mod d
else
d := d mod c;
gcd := c + d;
end;
begin
repeat
write(‘Two numbers: ‘);
readln(a,b);
writeln(‘GCD: ‘, gcd(a,b));
until (a = 0) and (b = 0);
end.
Two numbers: 56 18
GCD: 2
Two numbers: 196 144
GCD: 4
Two numbers: 305 809
GCD: 1
Two numbers: 810 3220
GCD: 10
Two numbers: 15000 10500
GCD: 1500
Two numbers: 0 200
GCD: 200
Two numbers: 0 0
GCD: 0
Язык Си
#include < stdio.h>
int gcd (int, int);
main() int a, b;
do printf(«Two numbers: «);
scanf(«%d%d», b);
printf(«GCD: %dn», gcd(a,b));
> while (a != 0 || b != 0);
>
int gcd(int c, int d) while (c != 0 d != 0) if (c > d) c = c % d;
else d = d % c;
>
return c + d;
>
Python
def gcd(c,d):
while c != 0 and d != 0:
if c > d:
c %= d
else:
d %= c
return c + d
a = b = 1
while a != 0 or b != 0:
a = input(«Two numbers: «)
a = a.split()
b = int(a[1])
a = int(a[0])
print(«GCD:», gcd(a,b))
КуМир
алг
нач
цел а, б
нц
вывод «Введите два целых числа: »
ввод а, б
вывод «НОД expert-review-faq-item expand»>
Basic-256
do
print «Введите два числа:»
input a
input b
gosub gcd
until a = 0 and b = 0
end
gcd:
c = a
d = b
while c<>0 and d<>0
if c>d then
c = c % d
else
d = d % c
endif
endwhile
print «НОД flat_pm_end»>
Источник: gospodaretsva.com