Напишите рекурсивную функцию которая вычисляет нод двух натуральных чисел используя алгоритм евклида

Напишите рекурсивную функцию которая вычисляет нод двух натуральных чисел используя алгоритм евклида

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2023. Stepik

Наши условия использования и конфиденциальности

Public user contributions licensed under cc-wiki license with attribution required

Реализация НОК и НОД на C++ (алгоритм Евклида)

Реализуем алгоритмы из статьи «Алгоритмы вычисления НОД и НОК» на языке С++. Первый (не самый эффективный вариант) вычисления НОД через многократное вычитание меньшего числа из большего:

unsigned int greatest_common_divisor(unsigned int a, unsigned int b) < if (a == b) return a; if (a >b) return greatest_common_divisor(a-b, b); return greatest_common_divisor(a, b-a); >

Более эффективный алгоритм вычисления НОД, использующий остаток от деления:

unsigned int greatest_common_divisor(unsigned int a, unsigned int b) < if (a % b == 0) return b; if (b % a == 0) return a; if (a >b) return greatest_common_divisor(a%b, b); return greatest_common_divisor(a, b%a); >

Функция вычисления НОК:

unsigned int least_common_multiple(unsigned int a, unsigned int b) < return (a*b)/greatest_common_divisor(a,b); >

31.10.2019 в 06:47 #6097

Вычислить НОД можно и без рекурсии. Код, приведнный ниже, был написан как пример к уроку по теме «Циклы в языке С++«. Задача: Реализуйте программу, вычисляющую наибольший общий делитель двух целых чисел (алгоритм Евклида). Решение:

#include using namespace std; int main() < int y, x; cin >> x >> y; while (x != y) < if (x>y) < x = x-y; >else < y = y-x; >> cout

Еще одна реализация алгоритма Евклида использует функцию swap : Перед разбором реализации на Пролог рекомендую посмотреть «Алгоритм Евклида (наибольший общий делитель)«. Ниже реализован вариант алгоритма с делением:

int NOD(int a, int b) < if (a < b) < swap(a, b); >while (a % b != 0) < a = a % b; swap(a, b); >return b; >

Функция swap выполняет обмен значений двух переменных. Она есть в стандартной библиотеке. Если в данный момент не понятно как она работает — замените ее на:

int t = a; a = b; b = t;

21.06.2021 в 19:39 #8105

Задача: Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива. Решение: Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел. Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, . аN) равен НОК(НОК(НОК(А1, А2), А3). АN) . Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут. Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):

#include #include void read_array(int n, int** values) < for (int i = 0; i < n; ++i) < printf("values[%d] = ", i); scanf("%d", &((*values)[i])); >> void print_array(int n, int* values) < for (int i = 0; i < n; ++i) < printf("values[%d] = %d\n", i, values[i]); >> void swap(int* a, int* b) < int tmp = *a; *a = *b; *b = tmp; >int gcd(int a, int b) < if (a < b) < swap(&a, &b); >while (a % b != 0) < a = a % b; swap(&a, &b); >return b; > int gcd_n(int n, int* values) < if (n == 0) return -1; if (n == 1) return values[0]; int gcd_value = gcd(values[0], values[1]); for (int i = 2; i < n; ++i) < gcd_value = gcd(gcd_value, values[i]); >return gcd_value; > int lcm(int a, int b) < return (a*b)/gcd(a, b); >int lcm_n(int n, int* values) < if (n == 0) return -1; if (n == 1) return values[0]; int lcm_value = lcm(values[0], values[1]); for (int i = 2; i < n; ++i) < lcm_value = lcm(lcm_value, values[i]); >return lcm_value; > int main()

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

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

Решение задачи на языке программирования Python

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 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 ) : . Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

Алгоритм нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.
2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 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

Нахождение наибольшего общего делителя

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

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

Алгоритм основан на том, что наибольший общий делитель пары чисел, не меняется, если из большего числа вычесть меньшее. Если повторять операцию вычитания, то в конце приходим к тому, что одно из чисел становится равным нулю, а второе является НОД.

Рекурсивная реализация поиска наибольшего общего делителя

Напишем два вспомогательных метода, которые возвращают минимальное и максимальное из двух чисел:

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 использованием вычитания

При каждом рекурсивном вызове вычитаем из максимального числа минимальное, повторяя рекурсивные вызовы до тех пор, пока первый аргумент не будет равен нулю:

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(); > > 

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

Для чисел 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.