Algoritmul lui Euclid

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

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

C și C ++

 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
}

C și C ++

 / * ALGORITM RECURSIV * /
int mcd ( int m , int n ) {
if ( n == 0 )
retur ( m );
altceva
returnează mcd ( n , m % n );
}

Scară

 @tailrec
def mcd ( m : Int , n : Int ) : Int =
if ( n == 0 )
m
altceva
mcd ( n , m % n )

MATLAB

 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

Piton

 def MCD ( a , b ):
    în timp ce b ! = 0 :
        a , b = b , a % b
    retur a

Rubin

euclid def ( a , b )
  în timp ce (b! = 0) do
    a , b = b , a % b
  Sfârșit
  retur a
Sfârșit

Pascal

 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.

PHP

 funcție mcd ( $ a , $ b ) {
	while ( $ b ) listă ( $ a , $ b ) = matrice ( $ b , $ a % $ b );
	returnează $ a ;
}

Merge

 func mcd ( a , b int ) int {
    pentru b ! = 0 {
        a , b = b , a % b
    }

    retur a
}

Notă

  1. ^ 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

Alte proiecte

linkuri externe

Controlul autorității GND ( DE ) 4659898-4
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică