Algoritmul lui Euclid
Algoritmul lui Euclid este un algoritm pentru găsirea celui mai mare divizor comun (notat mai jos cu GCD) între doi numere întregi . Este unul dintre cei mai vechi algoritmi cunoscuți, fiind prezent în elementele lui Euclid [1] în jurul anului 300 î.Hr .; cu toate acestea, algoritmul probabil nu a fost descoperit de Euclid , dar este posibil să fi fost cunoscut cu 200 de ani mai devreme. Cu siguranță a fost cunoscut de Eudossus din Cnidus în jurul anului 375 î.Hr .; Aristotel (în jurul anului 330 î.Hr. ) a menționat-o în I topici , 158b, 29-35. Algoritmul nu necesită factorizarea celor două numere întregi.
Având în vedere două numere naturale Și , verificați dacă este zero (această primă fază intră evident în sfera unei utilizări moderne a algoritmului și a fost ignorată de Euclid și de predecesorii săi, care nu știau zero). Dacă este, este MCD. Dacă nu este, se desparte și se atribuie restul diviziunii (operație indicată cu „a modulo b” mai jos). De sine atunci putem încheia afirmând că este MCD-ul pe care îl căutați, altfel trebuie să atribuiți Și iar împărțirea se repetă din nou. Algoritmul poate fi, de asemenea, exprimat în mod natural folosind recursivitatea cozii .
Luând notă de coeficienții obținuți în timpul execuției algoritmului, se pot determina două numere întregi Și astfel încât . Acest lucru este cunoscut sub numele de algoritmul Euclid extins .
Acești algoritmi pot fi folosiți, precum și cu numere întregi , în orice context în care este posibilă efectuarea împărțirii cu restul. De exemplu, algoritmul funcționează pentru polinoame cu un nedeterminat pe un câmp K sau polinoame omogene cu două nedeterminate pe un câmp sau cu numere întregi Gauss . Un obiect algebric în care este posibil să se împartă cu restul se numește inel euclidian .
Euclid a formulat inițial problema geometric, pentru a găsi o „măsură” comună pentru lungimea a două segmente, iar algoritmul său a procedat prin scăderea în mod repetat a celui mai scurt din cel mai lung. Această procedură este echivalentă cu următoarea implementare, care este mult mai puțin eficientă decât metoda de mai sus:
Dovada corectitudinii algoritmului
Lasa-i sa fie Și numere întregi pozitive atribuite, și așa să fie MCD-ul lor. Definim secvența de recurență corespunzătoare pașilor algoritmului lui Euclid: , , , Și este restul diviziunii pentru , acesta este . Prin definiția restului în diviziune, pentru fiecare , de aici și succesiunea lui este strict în scădere și, prin urmare, există un astfel încât . Vrem să arătăm asta . De fapt, prin inducție avem pentru fiecare acea . Mai mult, din nou prin inducție, împarte pentru fiecare , prin urmare se împarte și pentru fiecare , asa de .
Timp de calcul
Când analizăm timpul de calcul al algoritmului lui Euclid, constatăm că valorile de intrare care necesită cel mai mare număr de diviziuni sunt două numere succesive ale lui Fibonacci , iar cel mai rău caz necesită divizii O (n) , unde este numărul de cifre din intrare. De asemenea, trebuie remarcat faptul că diviziunile nu sunt operații atomice (dacă numerele sunt mai mari decât dimensiunea naturală a operațiilor aritmetice ale computerului), deoarece dimensiunea operanzilor poate fi de cifre. Atunci timpul real de calcul este atunci .
Acest timp este, totuși, considerabil mai bun decât algoritmul euclidian original, în care operația modulo este efectuată prin scădere repetată în pași. În consecință, această versiune a algoritmului necesită un timp egal cu pentru numerele cu cifre sau pentru număr .
Algoritmul lui Euclid este utilizat pe scară largă în practică, în special pentru numere mici, datorită simplității sale. Un algoritm alternativ, algoritmul MCD binar, folosește reprezentarea binară a computerelor pentru a evita diviziunile și, astfel, pentru a crește eficiența, deși și el este de ordinul : de fapt pe multe mașini reale permite scăderea constantelor ascunse în notația „O mare”.
Fracții continuate
Cotații care apar atunci când algoritmul euclidian este aplicat valorilor de intrare Și tocmai numerele apar în reprezentarea continuă a fracției a fracției . Luați exemplul Și folosit anterior. Acestea sunt calculele cu coeficienții evidențiați:
Din această listă puteți vedea asta
- .
Această metodă poate fi utilizată și pentru valori de Și real ; de sine este irațional, atunci algoritmul euclidian nu are sfârșit, dar secvența de coeficienți care este calculată constituie întotdeauna reprezentarea (acum infinită) a în fracție continuă.
Coduri
Acest articol sau secțiune referitoare la informatică este considerat a fi verificat . |
int Euclid ( int a , int b ) // prototip al funcției Euclid //
{
int r ;
în timp ce ( b ! = 0 ) // repetați până când reducem la zero
{
r = a % b ;
a = b ;
b = r ; // schimbăm rolul lui a și b
}
reveni la ; // ... și când b este (sau a devenit) 0, rezultatul este a
}
/ * ALGORITM RECURSIV * /
int mcd ( int m , int n ) {
if ( n == 0 )
retur ( m );
altceva
returnează mcd ( n , m % n );
}
@tailrec
def mcd ( m : Int , n : Int ) : Int =
if ( n == 0 )
m
altceva
mcd ( n , m % n )
funcţie afară = mygdc ( a, b )
dacă ( b == 0)
afară = a ;
elseif ( b == 1 )
afară = 1 ;
altceva
afară = mygdc ( b , mod ( a , b ));
Sfârșit
Sfârșit
def MCD ( a , b ):
în timp ce b ! = 0 :
a , b = b , a % b
retur a
euclid def ( a , b )
în timp ce (b! = 0) do
a , b = b , a % b
Sfârșit
retur a
Sfârșit
funcția MCD ( a , b : întreg ) : întreg ;
var r : întreg ;
începe
dacă b = 0 atunci
MCD : = a
altfel începe
r : = ( a mod b ) ;
în timp ce nu (r = 0) do
începe
a : = b ;
b : = r ;
r : = ( a mod b ) ;
sfârșit ;
GCD : = b ;
sfârșit ;
sfârșit ;
DE BAZĂ (vb.net)
Euclide_MCD Funcția (ByVal a Ca Int16, ByVal b Ca Int16) Ca Int16
Dim r Ca Int16 = a Mod b
While ( r <> 0 )
a = b
b = r
r = a Mod b
Termină În timp ce
Întoarcere b
Funcția de sfârșit
În acest algoritm, tipul "int16" a fost utilizat pentru reprezentarea numerică, dar poate fi schimbat cu orice alt tip de variabilă numerică în funcție de nevoile programului.
funcție mcd ( $ a , $ b ) {
while ( $ b ) listă ( $ a , $ b ) = matrice ( $ b , $ a % $ b );
returnează $ a ;
}
func mcd ( a , b int ) int {
pentru b ! = 0 {
a , b = b , a % b
}
retur a
}
Notă
- ^ F. Acerbi, Euclide, Toate lucrările , 2007, Bompiani . (EN) Thomas L. Heath , The Thirteen Books of Euclid's Elements, ed. A II-a. [Facsimil. Publicație originală: Cambridge University Press, 1925], 1956, Dover Publications
Bibliografie
- Donald Knuth ., Charles E. Leiserson, Ronald L. Rivest și Clifford Stein, Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Secțiunea 31.2: Cel mai mare divizor comun, pp. 856-862.
Elemente conexe
- Cel mai mic multiplu comun
- Cel mai mare divizor comun
- Ecuația diofantină liniară
- Ritmul lui Euclid
- Identitatea lui Bézout
Alte proiecte
- Wikimedia Commons conține imagini sau alte fișiere pe algoritmul lui Euclid
linkuri externe
- ( EN ) Algoritmul lui Euclid pentru tăierea nodului
- ( EN ) Algoritmul binar al lui Euclid (Java) pentru tăierea nodului
- ( RO ) Euclid's Game (Java) on cut-the-knot
Controlul autorității | GND ( DE ) 4659898-4 |
---|