Алгоритм Евклида с использованием деления и вычитания кратко

Лекция

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

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

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

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

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

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

Блок-схема Алгоритма Евклида вычитанием:

Алгоритм Евклида с использованием деления и вычитания

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

Код программы на C++ (вычитание):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include "stdafx.h"
#include
using namespace std;
//алгоритм Евклида. Вычитание
int NOD(int A, int B)
{
while (A!=B)
if (A>B) A-=B;
else B-=A;
return A;
}
//главная функция
void main ()
{
setlocale(LC_ALL,"Rus");
int A, B;
cout<<"A > "; cin>>A;
cout<<"B > "; cin>>B;
cout<<"НОД("<>void");
}

Код программы на Pascal (вычитание):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

program AlgEvklid;
uses crt;
var A, B: integer;
{алгоритм Евклида. Об этом говорит сайт https://intellect.icu . Вычитание}
function NOD(A, B: integer): integer;
begin
while A<>B do
if A>B then A:=A-B else B:=B-A;
NOD:=A;
end;
{основной блок программы}
begin
write('A > '); read(A);
write('B > '); read(B);
write('НОД(', A, ', ', B, ')=', NOD(A, B));
readkey;
end.

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

Второй способ отличается от первого тем, что в основной части программы операция вычитания заменяется на операцию деления, а точнее на взятие остатка от деления большого числа на меньшее. Этот способ предпочтительнее предыдущего, так как он в большинстве случаев эффективнее, требует меньше времени. На конкретных примерах продемонстрируем работу каждого из видов реализации алгоритма. Начнем с того, в основе которого лежит операция взятия остатка от деления. Имеем два числа: 112 и 32. Первое больше второго – заменим его остатком от деления 112 на 32. Новая пара чисел включает 16 и 32. Второе больше, поэтому также заменим его остатком от деления 32 на 16, т. е. нулем. В результате получаем НОД=16. Таблично это выглядит так:

Начальные данные	112	32
Шаг 1	16	32
Шаг 2	16	0

А теперь составим с теми же числами таблицу для алгоритма вычитанием.

Начальные данные	112	32
Шаг 1	80	32
Шаг 2	48	32
Шаг 3	16	32
Шаг 4	16	0

Приведенный пример продемонстрировал, как в частном случае, предпочтя деление (взятие остатка от деления) вычитанию, можно выиграть в быстродействии. Преимущество деления становится видно наиболее отчетливо после следующих рассуждений. Предположим, что A меньше B, а так как НОД двух целых чисел меньше или равен наименьшему из них, то и тут он меньше или равен A; поэтому оптимальным будет уже при первой операции заменить B числом меньшим или равным A. Далее, известно, что в одном случае большее число заменяется разностью его и меньшего числа, а в другом остатком от деления. При делении B на A (большее на меньшее), остаток не может превышать число, стоящее в знаменателе (т. е. A), следовательно, взятие остатка от деления гарантирует оптимальный исход. Но то же самое нельзя сказать в отношении операции вычитания, поскольку совсем необязательно, что сразу после выполнения первого вычитания, B станет меньше или равно A. К примеру, пусть A будет равняться 150, а B – 1100. Так, используя вычитание, мы в первом действии получим B равное 950, в то время как метод деления даст 50.

Блок-схема алгоритма Евклида делением:

Алгоритм Евклида с использованием деления и вычитания

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

Код программы на C++ (деление):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include "stdafx.h"
#include
using namespace std;
//алгоритм Евклида. Деление
int NOD(int A, int B)
{
while (A!=0 && B!=0)
if (A>B) A%=B; else B%=A;
return A+B;
}
//главная функция
void main ()
{
setlocale(LC_ALL,"Rus");
int A, B;
cout<<"A > "; cin>>A;
cout<<"B > "; cin>>B;
cout<<"НОД("<>void");
}

Код программы на Pascal (деление):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

program AlgEvklid;
uses crt;
var A, B: integer;
{алгоритм Евклида. Деление}
function NOD(a, B: integer): integer;
begin
while (A<>0) and (B<>0) do
if A>B then A:=A mod B
else B:=B mod A;
NOD:=A+B
end;
{основной блок программы}
begin
write('A > '); read(A);
write('B > '); read(B);
write('НОД(', A, ', ', B, ')=', NOD(A, B));
readkey;
end.

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

Из статьи мы узнали кратко, но содержательно про алгоритм евклида

Алгоритм Евклида с использованием деления и вычитания кратко

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

Код программы на C++ (вычитание):

Код программы на Pascal (вычитание):

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

Код программы на C++ (деление):

Код программы на Pascal (деление):

Комментарии

Оставить комментарий

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов