Un algoritm euclidian pentru găsirea unui nod

Euclid algoritmul este metoda de a găsi cel mai mare divizor comun pentru două numere.

Să luăm în considerare faptul că, dacă un număr natural dintr-o pereche împarte complet altul, atunci GCD-ul lor va fi egal cu cel mai mic dintre ele. Se poate scrie astfel: dacă a / b (întreg), atunci GCD (a; b) = b.

Luăm în considerare cel de-al doilea fapt. Dacă un număr este mai mare decât altul, atunci cel mai mare divizor comun este egal cu cel mai mare divizor comun pentru numărul mai mic al perechii, iar diferența dintre cele mai mari și mai mici. Este scris astfel: dacă a

Dovada că GCD (a; b) = GCD (a; b - a) poate fi după cum urmează. Fie b = a = c. Dacă un număr împarte a și b, atunci va împărți întregul și c. La urma urmei, dacă a și b sunt diferite, atunci divizorul din ele se potrivește întregului, dar un număr diferit de ori. Și dacă scădeți unul de celălalt, atunci divizorul trebuie să se potrivească, de asemenea, un număr întreg de ori în diferența care rezultă.

Dacă diminuăm secvențial a și b, atunci mai devreme sau mai târziu ajungem la valoarea celor mai mici, ceea ce va împărți mai mult. Cu atât mai mică într-o astfel de pereche va fi GCD pentru prima pereche de numere naturale. Acesta este algoritmul euclidian.

Să luăm în considerare un exemplu concret. Să fie necesar să găsească GCD (108, 72).

1. 108 nu este divizibil de 72. De aici obținem perechea 72 și 108 - 72 = 36
2. 72 este împărțit la 36. Aceasta înseamnă că GCD (108, 72) = 36.

Să găsim GCD (44, 60):

1. 60 nu este divizibil de 44. 60 - 44 = 16
2. 44 nu este divizibilă de 16. 44 - 16 = 28
3. 28 nu este divizibilă de 16. 28 - 16 = 12
4. 16 nu este divizibilă de 12. 16 - 12 = 4
5. 12 este împărțit la 4. Aceasta înseamnă că GCD (44, 60) = 4

Articole similare

• Acreditarea algoritmilor lucrătorilor medicali și a schemelor de trecere - юни месецд москва

Trimiteți-le prietenilor: