Нод и нок двух чисел, алгоритм евклида — студенческий портал

Давайте разберемся, что означает понятие «наибольший общий делитель».

Попробуем объяснить в не строгой форме.

Допустим у нас есть два числа, у этих двух чисел есть число, на которое они оба делятся. Максимально большое такое число и есть наибольшим общим делителем. Т.е. наибольший общий делитель – наибольшее число, на которое можно разделить несколько чисел без остатка. Строгое определение мы рассмотрим чуть позже.

Сейчас рассмотрим пример, который иллюстрирует данную идею:

У нас есть 48 шоколадок, и 36 конфет. Мы хотим из этого набора составить некоторые комплекты, которые мы подарим детям на Новый Год. Какое наибольшее количество комплектов мы можем сделать так, чтобы всем детям досталось поровну?

Решение:

Чтобы поделить шоколадки и конфеты поровну нам нужно разделить и шоколадки и кофеты нацело на количество подарков. Например, если поделить их на два подарка, то в каждом подарке будет по 24 шоколадки, и 18 конфет. То есть количество шоколадок или конфет нужно поделить на количество подарков, и оно будет делителем количества шоколадок или конфет.

Давайте найдем наибольший общий делитель чисел 48 и 36.

Выпишем все делители для обоих чисел:48:

• 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

•  Давайте выделим из них общие делители:
•  Наибольший из общих делителей – 12.
• Значит, мы можем сделать 12 подарков, и не сложно посчитать, что в каждом из них будет по 4 шоколадки, и по 3 конфеты.
• Ответ: 12 комплектов.
• Давайте дадим точное определение наибольшему общему делителю.
• Наибольший общий делитель(НОД)двух и более натуральных чисел – это наибольшее из натуральных чисел, на которое делится каждое из данных чисел.
• Есть два числа ,  их наибольший делитель будет записан так:

1. Числа в скобках написаны через точку с запятой, чтобы не путать числа с десятичной дробью.
2. Существует еще такая форма записи НОД:
3. Но чаще используют первый вариант.
4. Давайте подумаем в каких границах может находиться НОД двух чисел.
5. Первое свойство.
6. У любых двух чисел есть хотя бы один общий делитель, и это число 1.
7. И здесь мы введем понятие взаимно простых чисел.
8. Два числа называются взаимно простыми, если их наибольший общий делитель равен единице.

Что это значит? Это значит, что на самом деле у них нет других общих делителей, кроме единицы. Какие примеры взаимно простых чисел мы можем привести?

Например, числа 2 и 3, которые мы рассматривали выше. Числа 3 и 7 также взаимно простые.

Очень важно не путать понятия взаимно простых чисел, и простых чисел.

Из того что числа взаимно простые еще не следует, что они простые.

Например, . Тем не менее ни 9, ни 10 не являются простыми числами, но они взаимно простые.

Второе свойство.

Как вы думаете, если даны два числа  и , причем  нацело делится на  (), чему тогда равен ?

 – такое наибольшее число, на которое делятся и , и . Логично, что наибольшее число, на которое делится  – , а  – по условию.

Теперь давайте найдем удобный способ нахождения НОД.

В первом примере мы просто выписывали все числа, но такой способ не особо удобен при рассмотрении больших чисел. Давайте рассмотрим метод разложения на множители.

Рассмотрим все те же числа 36 и 48:

•  – это т.н. «каноническое разложение» числа 36;
• 

Давайте выделим общие множители столько раз, сколько они встречаются в результате разложения каждого числа: 2 ,2 ,3.

При перемножении этих чисел мы и получим НОД.

Ответ: 12.

Давайте рассмотрим другой пример.

Возьмем числа 25 и 40. Найдем НОД.

• ;
• Ответ: 5.
• Между прочим, если мы будем искать НОД трех чисел, то это делается без труда по такому же методу.
• Давайте попробуем на примере.
• Найти .

1. Ответ: 4;
2. Итак, мы с вами научились вычислять НОД двух чисел и трех чисел.
3. Давайте теперь рассмотрим еще несколько свойств НОД.

• ;

Вспомним, что такое простые числа. Простое число – это число, которое имеет ровно два натуральных делителя – единицу и себя.

• ; ,  – различные простые числа, следовательно эти числа – взаимно простые;
• ; т.е. последовательные числа также взаимно простые

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

Если взять числа больше, например, 143 и 257, разложение на множители уже не так очевидно, как в случае с 16 и 36, поэтому нужно найти универсальный метод, который бы работал для любых чисел, даже если разложение на множители затруднено. И такой универсальный метод есть. Он называется алгоритм Евклида. Этому алгоритму уже более двух тысяч лет, и тем не менее он радует глаз математиков и по сей день.

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

, т.к. .

Ответ 11.

Мы можем использовать этот алгоритм и для тех чисел, которые мы уже разобрали.

, т.к.

К сожалению, для трех чисел этот алгоритм настолько легко не работает. С другой стороны, у этого алгоритма есть несколько улучшений, есть алгоритм Евклида не с вычитанием, а с делением, поэтому если вам интересно, обязательно спросите у своего учителя, в чем он заключается и возможно вы сами сможете использовать этот более сильный метод.

Давайте не углубляясь разберемся, откуда же берется сама идея алгоритма с вычитанием. Наверняка вы знаете свойство делимости, что если два числа делятся на третье, то и сумма или разность двух чисел также делится на это третье, если  и , то . Это свойство мы здесь и используем.

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

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

Список рекомендованной литературы

1. Виленкин Н.Я., Жохов В.И., Чесноков А.С., Шварцбурд С.И. Математика 6. – М.: Мнемозина, 2012.

2.      Мерзляк А.Г., Полонский В.В., Якир М.С. Математика 6 класс. – Гимназия. 2006.

3. Депман И.Я., Виленкин Н.Я. За страницами учебника математики. – М.: Просвещение, 1989.

4. Рурукин А.Н., Чайковский И.В. Задания по курсу математика 5–6 класс. – М.: ЗШ МИФИ, 2011.

5. Рурукин А.Н., Сочилов С.В., Чайковский К.Г. Математика 5–6. Пособие для учащихся 6-х классов заочной школы МИФИ. – М.: ЗШ МИФИ, 2011.

6. Шеврин Л.Н., Гейн А.Г., Коряков И.О., Волков М.В. Математика: Учебник-собеседник для 5–6 классов средней школы. – М.: Просвещение, Библиотека учителя математики, 1989.

1. Рекомендованные ссылки на интернет ресурсы
2. Интернет портал «CleverStudents» (Источник)
3. Интернет портал «Фестиваль педагогических идей» (Источник)
4. Интернет портал «База презентаций» (Источник)
5. Рекомендованное домашнее задание
6. Найдите НОД чисел: 27, 15 и 9.
7. Найдите НОД (424;477) при помощи алгоритма Евклида.

Туристы проехали за первый день 56 км, а за второй – 72 км, причем их скорость была одинаковой и выражалась целым числом км/ч, и каждый день они были в пути целое число часов. Найдите скорость, с которой ехали туристы, если она была наибольшей из удовлетворяющих условию задачи.

Источник: https://interneturok.ru/lesson/matematika/6-klass/delimost-chisel/naibolshiy-obschiy-delitel-algoritm-evklida?seconds=0

Алгебра. Лекция 2. НОД и НОК. Алгоритм Евклида. Взаимно простые числа — презентация, доклад, проект

Слайд 1Описание слайда:

Лекция 2
НОД и НОК. Алгоритм Евклида. Взаимно простые числа

Слайд 2Описание слайда:

Задача 1
Камин в комнате необходимо выложить отделочной плиткой квадратной формы. Сколько плиток понадобится для камина размером 195ˣ156 см. Каковы наибольшие размеры плитки? Решение: 195∙156=30420 (см²) – S поверхности камина НОД (195 и 156)=39 (см) – сторона плитки 39 ∙39=1521 (см²) – S одной плитки 30420:1521=20 (штук) Ответ: 20 плиток размером 39ˣ39 см.

Слайд 3Описание слайда:

НОД Определение 1. Число d называется общим делителем чисел a1, a2,…, an, если a1⁞d, a2⁞d,…, an⁞d Определение 2.

Наибольшим общим делителем целых чисел a1, a2,…, an называется такой их общий натуральный делитель, который делится на любой их общих делитель Обозначают: d=(a1, a2,…, an) d=(a1, a2,…, an), если d ϵ N d – общий делитель чисел a1, a2,…, an если с – общий делитель чисел a1, a2,…,an, то d⁞c Примеры (16, 30, 12)=2 (21, 15, 48)=3

Слайд 4Описание слайда:

Задача 2
В портовом городе начинаются три туристических теплоходных рейса, первый из которых длится 15 суток, второй – 20 и третий – 12 суток. Вернувшись в порт, теплоходы в этот же день снова отправляются в рейс.

Сегодня из порта вышли теплоходы по всем трем маршрутам.

Через сколько суток они впервые снова вместе уйдут в плавание? Какое количество рейсов сделает каждый теплоход? Решение: НОК (15, 20 и 12)=60 (суток) – время встречи 60:15=4 (рейса) – 1 теплоход 60:20=3 (рейса) – 2 теплоход 60:12=5 (рейсов) – 3 теплоход

Слайд 5Описание слайда:

НОК Определение 3. Число М называется общим кратным целых чисел a1, a2,…, an, если оно делится на каждое из этих чисел Определение 4.

Наименьшим общим кратным целых чисел a1, a2,…, an называется такое их общее натуральное кратное m, которое делит любое их общее кратное Обозначают: m=[a1, a2,…, an] m=[a1, a2,…, an], если m ϵ N m – общее кратное чисел a1, a2,…, an если М – общее кратное чисел a1, a2,…, an, то М⁞m Примеры: [16, 30, 12]=16∙5∙3=240; [21, 15, 48]=48∙5∙7

Слайд 6Описание слайда:

Лемма Если a, b ϵ Z, b≠0 и a=bq+r, то (a,b)=(b,r) Доказательство Пусть (a,b)=d1, (b,r)=d2 Так как a⁞d1, b⁞d1, то (r=a-bq) ⁞d1 Следовательно, d1 – общий делитель чисел b и r, поэтому их наибольший общий делитель d2=(b,r) ⁞d1 Так как b⁞d2, r⁞d2, то a⁞d2 и d2 – общий делитель чисел a и b Поэтому d1⁞d2 Из того, что d1⁞d2, d2⁞d1 и d1, d2 ϵ N, следует, что d1=d2

Слайд 7Описание слайда:

Алгоритм Евклида Пусть a, b ϵ Z, b≠0. По теореме о делении с остатком a=bq1+r1, где 0 ≤ r1 < │b│. Если r1≠0, то b=r1q2+r2, где 0 ≤ r2 < r1. Если r2≠0, то r1=r2q3+r3, где 0 ≤ r3 < r2. И так далее …………......

rn-2=rn-1qn+rn, где 0 < rn < rn-1 rn-1=rn qn+1+rn+1 Этот процесс не может быть бесконечным, так как не может быть бесконечной убывающей последовательности неотрицательных чисел: │b│> r1 > r2 >…> rn , rn+1 ϵ [0, │b│] Поэтому после нескольких шагов получим остаток, равный нулю Пусть rn+1=0

Слайд 8Описание слайда:

Теорема Последний не равный нулю остаток в алгоритме Евклида, применённый к целым числам a и b, где b≠0, есть их наибольший общий делитель (НОД) Доказательство Применяя лемму к первому, второму и так далее равенствам алгоритма Евклида, имеем: (a, b) = (b, r1) = (r1, r2) = … = (rn-1, rn) = rn, так как rn-1⁞rn Из теоремы следует существование НОД двух чисел, если хотя бы одно из них не равно нулю

Слайд 9Описание слайда:

Свойства НОД Если a⁞b, то (a, b) = │b│ Если (a, b) = d, то существуют u, v ϵ Z, что d=au+bv (линейная форма НОД) 3) Если (a, b)=d, n ϵ N, то (na, nb)=nd 4) Если (a, b)=d, a⁞n, b⁞n, n ϵ N, то В частности, 5) (a1, a2, …, an) = ((a1, a2, …, an-1), an)

Слайд 10Описание слайда:

Примеры Найдём НОД чисел a и b и выразим его линейно через эти числа a=1173, b=323; a= 3∙b+r1, r1=204; b=1∙r1+r2, r2=119; r1=r2+r3, r3=85; r2=r3+r4, r4=34; r3=2∙r4+r5, r5=17; r4=2∙r5. Итак, (a, b)=d=17. Выразим его линейно через a и b.

Из первого равенства r1=a-3b. Подставив в равенство для b, находим r2=b-r1=-a+4b. Далее: r3=r1-r2=2a-7b; r4=r2-r3=-3a+11b; d=r5=r3-2r4=8a-29b a=1403, b=1058; 1403=1058+345; 1058=345∙3+23; 345=23∙15. НОД чисел a и b равен 23.

23=1058-345∙3=1058-(1403-1058)∙3=-3∙1403+4∙1058=-3a+4b

Слайд 11Описание слайда:

Свойства НОК [a1, a2, …, an]=[[ a1, a2, …, an-1], an] Если к – натуральное, то [ak, bk]=k[a, b] Если k = натуральное, a⁞k, b⁞k, то Если (a, b)=1, то [a, b] = ab

Слайд 12Описание слайда:

Взаимно простые числа Числа a1, a2, …, an называют взаимно простыми, если наибольший общий делитель этих чисел равен 1 Примеры 1) 15, 21, 14 – взаимно простые числа, однако эти числа не являются попарно взаимно простыми 2) 34, 53, 99, 115 – попарно взаимно простые числа, так как взаимно простые каждые два числа этого ряда

Слайд 13Описание слайда:

Свойства взаимно простых чисел (Признак взаимно простых чисел) (a, b)=1 тогда и только тогда, когда найдутся целые u и v, что au+bv=1 2) Если (a, b)=1 и (a, c)=1, то (a, bc)=1 Доказательство. Согласно признаку, существуют целые числа x, y, u, v, что ax+by=1 и au+cv=1. Перемножив эти равенства, получим a(axu+xcv+buy)+bc(yv)=1, то есть au1+bcv1=1 или (a, bc)=1

Слайд 14Описание слайда:

Свойства взаимно простых чисел 3) Если ab⁞c и (a, c)=1, то b⁞c Доказательство. Существуют целые числа u, v, что au+cv=1. Умножим обе части равенства на b: abu+cbv=b.

Так как a⁞b, c⁞c, то ac⁞bc. Следовательно, (abu+acv)⁞bc и a⁞bc

Источник: https://myslide.ru/presentation/skachat-algebra-lekciya-2-nod-i-nok-algoritm-evklida-vzaimno-prostye-chisla

Расширенный алгоритм Евклида

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

Т. е. он находит коэффициенты, с помощью которых НОД двух чисел выражается через сами эти числа.

Калькулятор ниже, а описание алгоритма, как водится, под ним.

Коэффициент перед большим числом

Коэффициент перед меньшим числом

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

1. — результат целочисленного деления b на a,
2. и подставим в выражение:
3. Выполнив перегруппировку слагаемых, получим:
4. Сравнивая это с исходным выражением над неизвестными x и y, получаем требуемые выражения:

Выход из рекурсии — конец обычного алгоритма, случай a = 0. НОД, соответственно, равен b, и требуемые коэффициенты x и y равны 0 и 1 соответственно. Дальше идет вычисление по формулам.

Источник: https://planetcalc.ru/3298/

8 способов нахождения наибольшего общего делителя

Эта статья появилась на свет совершенно неожиданно. Мне на глаза случайно попался код вычисления НОД на C#.

С первого взгляда мне даже всё понравилось: простенько, лаконичненько и без лишнего выпендрёжа. Однако чем дольше я рассматривал этот код, тем больше возникало сомнений в его эффективности. Я решил сделать маленькое исследование.

В адаптации на C++ код выглядел примерно так:

#include

using namespace std;

int main() {

int a, b;
cin >> a >> b;
for (int i = a; i > 0; i—) {
if (a % i == 0 && b % i == 0) {
cout b ? b : a;
}

long gcd02(long a, long b) {

long nod = 1L;
for (long i = min(a, b); i > 0; i—) {
if (a % i == 0 && b % i == 0) {
nod = i;
break;
}
}
return nod;
}

Просто добавляем простейшую функцию для вычисления минимального числа для пары чисел и инициализируем переменную цикла меньшим из двух чисел. В половине случаев такая оптимизация работать не будет (когда первый аргумент и так меньше второго); зато в другой половине случаев выигрыш по времени может быть весьма значительным.

03 алгоритм с разложением на делители

Но второй вариант так и остался алгоритмом с последовательным перебором. Что можно попробовать ещё?

Из школьного курса математики известно, что НОД можно найти из разложения чисел на простые множители.

a = m1 * m2 * m3 * … * mN
где m – простые числа

НОД будет равен произведению простых множителей, общих для обоих чисел. Например:

24 = (2) * 2 * 2 * (3)
54 = (2) * (3) * 3 * 3

общие множители выделены скобками

НОД(24, 54) = 2 * 3 = 6

Реализуем эту идею:

long gcd03(long a, long b) {

long nod = 1L;

if (a > b) {
long tmp = a;
a = b;
b = tmp;
}

while (a > 1L && b > 1L) {
for (long i = 2; i b) {
long tmp = a;
a = b;
b = tmp;
}
return gcd04(a, b — a);
}

Считается, что рекурсивные алгоритмы менее эффективны, чем итерационные, за счёт накладных расходов на вызов функции. Для проверки делаем и итерационный вариант.

05 алгоритм Евклида (итерационный)

long gcd05(long a, long b) {

while (a != b) {
if (a > b) {
long tmp = a;
a = b;
b = tmp;
}
b = b — a;
}
return a;
}

Кстати, в Викиучебнике есть и другие реализации алгоритма Евклида.

06 бинарный алгоритм (рекурсивный)

Бинарный алгоритм Евклида.

1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
2. НОД(1, n) = 1; НОД(m, 1) = 1;
3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
6. Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
7. Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);

Рекурсивная версия:

long gcd06(long a, long b) {
if (a == 0L)
return b;
if (b == 0L)
return a;
if (a == b)
return a;
if (a == 1L || b == 1L)
return 1L;
if (a % 2L == 0L && b % 2L == 0L)
return 2L * gcd06(a / 2L, b / 2L);
if (a % 2L == 0L && b % 2L != 0L)
return gcd06(a / 2L, b);
if (a % 2L != 0L && b % 2L == 0L)
return gcd06(a, b / 2L);
if (a < b) return gcd06((b - a) / 2L, a); else return gcd06((a - b) / 2L, b); }

07 бинарный алгоритм (итерационный)

Итерационная версия:

long gcd07(long a, long b) {
long nod = 1L;
long tmp;
if (a == 0L)
return b;
if (b == 0L)
return a;
if (a == b)
return a;
if (a == 1L || b == 1L)
return 1L;
while (a != 0 && b != 0) {
if (a % 2L == 0L && b % 2L == 0L) {
nod *= 2L;
a /= 2L;
b /= 2L;
continue;
}
if (a % 2L == 0L && b % 2L != 0L) {
a /= 2L;
continue;
}
if (a % 2L != 0L && b % 2L == 0L) {
b /= 2L;
continue;
}
if (a > b) {
tmp = a;
a = b;
b = tmp;
}
tmp = a;
a = (b — a) / 2L;
b = tmp;
}
if (a == 0)
return nod * b;
else
return nod * a;
}

Кстати, в Викиучебнике есть и другие реализации бинарного алгоритма Евклида.

08 бинарный алгоритм (итерационный) с использованием битовых операций

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

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

long gcd08(long a, long b) {
long nod = 1L;
long tmp;
if (a == 0L)
return b;
if (b == 0L)
return a;
if (a == b)
return a;
if (a == 1L || b == 1L)
return 1L;
while (a != 0 && b != 0) {
if (((a & 1L) | (b & 1L)) == 0L) {
nod = 1L;
b >>= 1L;
continue;
}
if (((a & 1L) == 0L) && (b & 1L)) {
a >>= 1L;
continue;
}
if ((a & 1L) && ((b & 1L) == 0L)) {
b >>= 1L;
continue;
}
if (a > b) {
tmp = a;
a = b;
b = tmp;
}
tmp = a;
a = (b — a) >> 1L;
b = tmp;
}
if (a == 0)
return nod * b;
else
return nod * a;
}

Ещё немного подготовки

Итак, функции, на которые хватило времени, мозгов и фантазии написаны. Можно допиливать «испытательный стенд» и приступать к тестированию.

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

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

Получилось, что даже если изначально в паре числа были взаимно просты, то алгоритм поиска НОД должен будет вычислить именно этот добавленный множитель.

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

#include
#include
#include
#include

using namespace std;

//
// здесь должны быть определения функций вычисления НОД
//

struct sub {
long(*func)(long, long);
const char * comm;
};

sub arr[] = {
{ gcd01, «01 перебор от произвольного числа » },
{ gcd02, «02 перебор от минимального числа » },
{ gcd03, «03 с разложением на делители » },
{ gcd04, «04 алгоритм Евклида рекурсивный » },
{ gcd05, «05 алгоритм Евклида итерационный » },
{ gcd06, «06 бинарный алгоритм рекурсивный » },
{ gcd07, «07 бинарный алгоритм итерационный » },
{ gcd08, «08 бинарный алгоритм итерац. со сдвигом » }
};

const unsigned int RAND_TIMES = 500u;
const unsigned long REPEAT_TIMES = 10000uL;

int main() {

clock_t the_time;
double elapsed_time;

setlocale(LC_ALL, «Russian»);

long a, b, c, nod;

srand((unsigned int)time(NULL));
double times[sizeof(arr) / sizeof(sub)] = { 0.0 };

for (unsigned int t = 0u; t < RAND_TIMES; t++) { c = rand() % 50 + 1; a = (rand() % 1000 + 1) * c; b = (rand() % 1000 + 1) * c; for (unsigned int alg = 0u; alg < sizeof(arr) / sizeof(sub); alg++) { the_time = clock(); for (unsigned long m = 0uL; m < REPEAT_TIMES; m++) { nod = arr[alg].func(a, b); } elapsed_time = double(clock() - the_time) / CLOCKS_PER_SEC; times[alg] += elapsed_time; } printf("%4u НОД(%7ld, %7ld) = %7ld ", t + 1, a, b, nod); } printf(" Среднее время для %d пар случайных чисел: ", RAND_TIMES); for (unsigned int alg = 0; alg < sizeof(arr) / sizeof(sub); alg++) { printf("%s: %8.4f сек. ", arr[alg].comm, times[alg] / RAND_TIMES); } return 0; }

Тестирование

Программа компилировалась под MS Visual Studio 2013 и TDM-GCC 4.8.1 в режиме 64-bit Release.

Среднее время для 500 пар случайных чисел:
——————————————————-
01 перебор от произвольного числа : 0.5022 сек.
02 перебор от минимального числа : 0.3256 сек.
03 с разложением на делители : 0.0063 сек.
04 алгоритм Евклида рекурсивный : 0.0007 сек.
05 алгоритм Евклида итерационный : 0.0008 сек.
06 бинарный алгоритм рекурсивный : 0.0006 сек.
07 бинарный алгоритм итерационный : 0.0003 сек.
08 бинарный алгоритм итерац. со сдвигом : 0.0002 сек.

Как и ожидалось, первый алгоритм катастрофически неэффективен. Алгоритм №2 – минимальный костыль для №1 – работает почти в 2 раз быстрее.

Третий алгоритм неожиданно показал очень достойный результат: в 50 раз быстрее алгоритма №2.

Бинарный алгоритм Евклида показал наилучшие результаты. Из трёх вариантов реализации рекурсивная версия – самая неторопливая. Наилучший результат у оптимизированной версии с использованием битовых операций.

Итого, самая производительная версия работает более чем в 2500 раз быстрее, чем изначальный вариант.

Примечание. Время, указанное в таблице – это время выполнения REPEAT_TIMES вызовов функции.

Выводы

Выводы достаточно банальны, но всё же:

1. Первый пришедший на ум алгоритм решения какой-то задачи часто неоптимален. Хотя и может правильно и достаточно приемлемо работать в определённых условиях.
2. Всегда надо попробовать подумать над усовершенствованием алгоритма или над альтернативным вариантом.
3. Учите математику!
4. Если есть возможность, посмотрите что сделали люди до вас. Может не стоит изобретать велосипед?
5. Оптимизируйте код.

Cranium aka Череп

Источник: https://code-live.ru/post/greatest-common-denominator-algorithms/

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

☰

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

Наибольший общий делитель пары чисел – это самое большое число, которое нацело делит оба числа пары. Пусть требуется вычислить НОД для чисел 108 и 72. Алгоритм вычисления делением будет таковым:

1. Разделим большее число (делимое) на меньшее (делитель): 108 / 72 = 1, остаток 36.
2. Поскольку остаток не был равен нулю, то сделаем делитель делимым, а остаток – делителем: 72 / 36 = 2, остаток 0.
3. Когда остаток равен нулю, то делитель является искомым НОД для пары заданных чисел. То есть НОД(108, 72) = 36. Действительно, 108 / 36 = 3 и 72 / 36 = 2.

В данном алгоритме деление повторяется до тех пор, пока остаток не станет равным нулю. Когда он таковым становится, НОДом является делитель последнего деления. Например, требуется найти НОД(106, 16):

1. 106 / 16 = 6, остаток 10
2. 16 / 10 = 1, остаток 6
3. 10 / 6 = 1, остаток 4
4. 6 / 4 = 1, остаток 2
5. 4 / 2 = 2, остаток 0
6. НОД(106, 16) = 2

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

Пусть требуется найти НОД(108, 72):

1. 108 — 72 = 36
2. 72 — 36 = 36
3. 36 — 36 = 0
4. НОД(108, 72) = 36

Найдем НОД(44, 60):

1. 60 — 44 = 16
2. 44 — 16 = 28
3. 28 — 16 = 12
4. 16 — 12 = 4
5. 12 — 4 = 8
6. 8 — 4 = 4
7. 4 — 4 = 0
8. НОД(44, 60) = 4

Данный алгоритм иногда описывают по-другому. Вычитание заканчивают раньше, на шаге, когда одно число нацело делит другое. То есть комбинируют вычитание с проверкой делимости. Тогда нахождение НОД для 44 и 60 будет выглядеть так:

1. Делит ли 44 нацело 60? Нет. 60 — 44 = 16.
2. Делит ли 16 нацело 44? Нет. 44 — 16 = 28.
3. Делит ли 16 нацело 28? Нет. 28 — 16 = 12.
4. Делит ли 12 нацело 16? Нет. 16 — 12 = 4.
5. Делит ли 4 нацело 12? Да. Значит, НОД(44, 60) = 4.

Обратите внимание, НОДом является не частное, а делитель. Если в примере мы разделим 12 на 4, то получим частное 3. Но это не НОД.

Примем во внимание факт, что если одно натуральное число из пары нацело делит другое, то их НОД будет равен меньшему из них. Записать это можно так:

если a / b нацело, то НОД(a, b) = b. Например, НОД(15, 5) = 5.

Таким образом, если в конечном итоге мы приходим к паре чисел, одно из которых делит нацело другое, то меньшее будет для обоих наибольшим общим делителем. Именно такая пара чисел ищется алгоритмом Евклида: одно число нацело делит другое.

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

если a < b, то НОД(a, b) = НОД(a, b - a).

Доказать, что НОД(a, b) = НОД(a, b — a) можно следующим образом. Пусть b — a = c. Если какое-либо число x делит нацело a и b, то оно будет также делить нацело c. Ведь если a и b различны, то делитель в них укладывается целое, но разное число раз. И если вычесть одно из другого, то делитель также должен укладываться целое число раз в полученную разность.

Если последовательно уменьшать a и b, то рано или поздно придем к такому значению меньшего из них, которое нацело делит большее. Меньшее в такой паре будет наибольшим общим делителем для исходной пары натуральных чисел. В этом и заключается алгоритм Евклида.

Copyright © 2019. All Rights Reserved

Источник: https://scienceland.info/algebra8/euclid-algorithm