Алгоритъм на Евклид
Съдържание
НОД - най-голям общ делител (чрез изваждане) с итерация
НОД - най-голям общ делител (чрез изваждане) с рекурсия
НОД - най-голям общ делител (чрез делене)
взаимно прости числа
НОК - най-малко общо кратно
естествено число - прости делители
Един от най-старите известни алгоритми е свързан с намиране на най-голям общ делител на две естествени числа (НОД).
Среща в литературата под името алгоритъм на Евклид (Euclidean algorithm).
За този алгоритъм е доказано: винаги завършва с определен резултат; броят на необходимите изваждания винаги е по-малък от стойността на по-голямото от двете естествени числа. Тук ще опишем както самия алгоритъм, така и решение на задача извеждаща най-големия общ делител.
Пример най-голям общ делите на 45 и 75:
45 75 НОД=15
НОД - най-голям общ делител (чрез изваждане) с итерация
Нека разгледаме примерно решение на тази задача в два варианта.
Общото между тях е наличие на цикличен процес.
Чрез изваждане - от по-голямото число се вади по-малкото до достигане на резултат 0, т.е. до
равенство на двете числа.
Най-големият общ делител е останалото по-голямо число.
Следи се винаги да се изважда от по-голямото число по-малкото.
Следва сорс код на примерна програма (DEV C++), съдържаща решение на задача за алгоритъм на Евклид (чрез изваждане) с итерация.
#include<iostream>
using namespace std;
int euclid_I(int M, int N) // euclidean algorithm
{
while (M!=N)//dokato razlikata mevdu chislata e <> 0
{ cout<<"W momenta chislata sa: "<<M<<":"<<N<<endl;
if (M>N) M-=N; else N-=M;//rawnostojnoto if (M>N) M=M-N; else N=N-M;
}//while
return M;
}//euclid
int main()//nachalo na programata
{ int M,N;
cout<<"Da se systawi programa, chrez koqto se izwevda naj-golemiq obsh\n";
cout<<"delitel na dwe estestweni chisla. Prilovete algoritym na Ewklid.\n";
cout<<"Primer: 28, 35 Izhod: 7 \n";
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>M;
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>N;
cout<<"Naj-golemiqt obsh delitel e: "<<euclid_I(M, N)<<endl;
system("pause");//chaka natiskane na klawish ot klawiaturata
return 0; //oswobovdawa zaetite sistemni resursi
} //kraj na programa algoritym na Ewklid
Начало на страницата
НОД - най-голям общ делител (чрез изваждане) с рекурсия
Следва сорс код на примерна програма, съдържаща решение на задача за алгоритъм на Евклид (чрез изваждане) с рекурсия.
#include<iostream>
using namespace std;
int euclid_R(int M, int N)
{ //algoritym na Ewklid (euclidean algorithm) - ot po-golqmoto chislo se wadi po-malkoto
//dokato dwete chisla stanat rawni
if (M!=N) //uslowie za kraj na rekursiqta
{cout<<"Systoqnie na dwete chisla: "<<M<<":"<<N<<endl;
if (M>N) return euclid_R(M-N,N);
else return euclid_R(M,N-M);
}// (M!=N)
return M;
}//int euclid_R
int main()//nachalo na programata
{ int M,N;
cout<<"Da se systawi programa, chrez koqto se izwevda naj-golemiq obsh\n";
cout<<"delitel na dwe estestweni chisla. Prilovete algoritym na Ewklid.\n";
cout<<"Primer: 28, 35 Izhod: 7 \n";
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>M;
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>N;
cout<<"Naj-golemiqt obsh delitel e: "<<euclid_R(M, N)<<endl;
system("pause");//chaka natiskane na klawish ot klawiaturata
return 0; //oswobovdawa zaetite sistemni resursi
} //kraj na programa naj-golqm delitel Ewklid
Начало на страницата
НОД - най-голям общ делител (чрез делене)
Аналогично на алгоритъма чрез изваждане може да се приложи делене - отново по-голямото число се дели на по-малкото до достигане на на целочислен остатък равен на 0, т.е. едното число се явява кратно на другото.
Най-големият общ делител е останалото по-голямо число.
На всяка стъпка стойностите на двете числа се променят: по-голямото присвоява стойността на
по-малкото, а по-малкото на целочисленото частно.
Преди началото на цикличния процес се определя по-голямото въведено число.
Тази част от програмата може да се замени с условен оператор.
Следва сорс код на примерна програма, съдържаща решение на задача за алгоритъм на Евклид чрез делене.
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int a1,a2,Min, Max,ob;
cout<<"Da se systawi programa, chrez koqto se wywevdat dwe estestweni chisla\n";
cout<<"ot interwala [2..1001]. Programata da izwevda tehniq naj-golqm obsh delitel \n";
cout<<" NOD, chrez algoritym na Ewklid - s delene.\n";
cout<<"Primer 36,24 Izhod: 12\n";
cout<<"Wywedete stojnostta na promenliwa 1 A= "; cin>>a1;
cout<<"Wywedete stojnostta na promenliwa 2 B= "; cin>>a2;
//sys sledwashite dwa reda opredelqme po-golqmoto i po-malkoto ot wywedenite chisla
Max= ((a1+a2) - abs(a1-a2))/2;//po-golqmoto chislo
Min= ((a1+a2) + abs(a1-a2))/2;
ob = Max % Min;//celochisleno delene, ako ob==0, to NOD = Min
// Ewklid algorithm
while (ob)//dokato ne se nameri kratno
{
Max = Min;
Min = ob;
ob= Max % Min;
}//while
if (Min-1)
cout<<"HOD ("<<a1<<",
"<<a2<<")= "<<Min<<endl;
else cout<<"Chislata "<<a1<<", "<<a2<<" sa wzaimno prosti. NOD = 1. \n";
system("pause");
return 0;
}//kraj na programa naj-golqm obsh delitel Ewklid
Начало на страницата
взаимно прости числа
Две или повече числа, на които най-големият общ делител е 1, се наричат взаимно прости числа.
Пример: числата 21 и 16 са взаимно прости числа, защото НОД (21, 16) = 1.
Бихме могли да изведем характерни признаци за взаимно прости числа:
а) ако едно от двете числа е просто, то двете числа са взаимно прости;
б) ако са последователни естествени числа.
Ако две числа са прости, те са взаимно прости числа, обратното твърдение не е вярно.
Геометрично представяне: нека е зададена точка с M с координати (x,y) – цели числа.
Ако в декартова координатна система построим отсечка с начало (0,0) и край (x,y) и на отсечката не принадлежи друга точка с координати цели числа, казваме че x,y са взаимно прости числа.
Алгоритъмът за проверка дали две числа са взаимно прости използва алгоритъм на Евклид за намиране на най-голям общ делител - НОД.
Ако изчисленият НОД на двете числа е 1, то те са взаимно прости числа.
Следва примерна програма, съдържаща решение на задача за взаимно прости числа:
#include<iostream>
using namespace std;
int euclidean_NOD(int M, int N) // naj-golqm obsh delitel Ewklid
{
while (M!=N)//dokato razlikata mevdu chislata e <> 0
{ if (M>N) M-=N; else N-=M;//rawnostojnoto if (M>N) M=M-N; else N=N-M;
}//while
return M;
}// naj-golqm obsh delitel
int main()
{ int M,N,obsh;
char ose;
cout<<"Da se systawi programa, chrez koqto se prowerqwa dali dwe \n";
cout<<"estestweni chisla N i M sa wzaimno prosti.\n";
cout<<"Primer: 28, 33 Izhod: Da \n";
do {
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>M;
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>N;
obsh=euclidean_NOD(M, N);
if (obsh==1) cout<<"Chislata sa wzaimno prosti.\n";
else cout<<"Naj-golemiqt obsh delitel na dwete chisla e: "<<obsh<<endl;
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
}while (ose=='y');
system("pause");
return 0;
} //kraj na programa naj-golqm obsh delitel Ewklid
Начало на страницата
НОК - най-малко общо кратно
Число, което е кратно на няколко дадени числа, се нарича тяхно общо кратно.
Най-малкото от общите кратни на две или повече числа се нарича най-малко общо кратно на тези числа.
Алгоритъмът за най-малко общо кратно използва алгоритъм на Евклид за намиране на най-голям общ делител.
Така НОК на две естествени числа N, M с НОД P се получава като отношение между произведенията на двете числа M*N и техния най-голям общ делител P.
НОК = M * N / P
Пример: НОК на 14 (2*7) и 21 (3*7) е = 42 (2*3*7)
Пример: 36, 48
Изход: НОК = 144, т.к 36=12*3, 48=12*4, 144=12*3*4
Ако трябва да се обобщи алгоритъма за най-малко общо кратно за повече от две числа A1,A2,A3...An, то формулата би изглеждала НОК = НОД*(A1/НОД)*(А2/НОД) *...* (An/НОД)
Най-малкото общо кратно на две взаимно прости числа е тяхното произведение. Пример: 3 и 5, то най-малко общо кратно НОК = 15
Следва примерна програма, съдържаща решение на задача за намиране на най-малко общ кратно на две естествени числа:
#include<iostream>
using namespace std;
int euclidean_NOK(int M, int N) // Ewklid algorithm
{
while (M!=N)//dokato razlikata mevdu chislata e <> 0
{ if (M>N) M-=N; else N-=M;//rawnostojnoto if (M>N) M=M-N; else N=N-M;
}//while
return M;
}//naj-malko obsho kratno Ewklid
int main()//nachalo na programata
{ int M,N,obsh,NOK;
char ose;
cout<<"Da se systawi programa, chrez koqto se namira \n";
cout<<" nai-malko obsho kratno na dwe estestweni chisla N i M.\n";
cout<<"Primer: 45, 75 Izhod: 225 \n";
do {
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>M;
cout<<"Wywedete estestweno chislo ot interwala [3..1001]: ";cin>>N;
obsh=euclidean_NOK(M, N);
cout<<"NOD = "<<obsh<<endl;
NOK=M*N/obsh;
cout<<"naj-malko obsho kratno na "<<M<<" i "<<N<<" e "<<NOK<<endl;
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
}while (ose=='y');
system("pause");
return 0;
} //kraj na programa nai-malko obsho kratno Ewklid
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата и последователните стъпки в алгоритъм на Евклид за изчисляване на НОД е даден в предоставените електронни помагала съдържащи решени задачи, примери.
Начало на страницата
