Back خوارزمية أقليدس Arabic Algoritmu d'Euclides AST Evklid alqoritmi Azerbaijani Евклид алгоритмы Bashkir Алгарытм Эўкліда Byelorussian Алгоритъм на Евклид Bulgarian ইউক্লিডীয় এলগরিদম Bengali/Bangla ئەلگۆریتمی ئیقلیدس CKB Eukleidův algoritmus Czech Algorithm Ewclidaidd Welsh

Algorisme d'Euclides

L'algorisme d'Euclides[a] és un mètode eficaç per a calcular el màxim comú divisor (mcd) entre dos nombres enters. Rep el nom del matemàtic grec Euclides el qual el va descriure en els volums VII i X del llibre Elements.[1]

L'algorisme consisteix en diverses divisions enteres successives. En la primera divisió, es pren com a dividend el major dels nombres i com a divisor l'altre. Després, el divisor i el residu serveixen respectivament de dividend i divisor de la següent divisió. El procés es para quan s'obté un residu nul. El mcd és llavors el penúltim residu de l'algorisme.[2]
Formalment, si anomenem a, b els enters inicials, r1, rn ... rn-1 i rn = 0 els residus successius, llavors:

mcd (a, b) = mcd (b, r1), amb r1 = a - b·q (q és el quocient de a per b)

Després el menor dels divisors comuns és el mateix, i repetint l'operació:

mcd (b, r1) = mcd (r1, r₂) = mcd (r₂, r₃) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) = rn-1.

Això permet detallar l'algorisme efectiu:

  • dades d'entrada a i b  - si cal, canvieu-los a positius
  • l'algorisme:
mentre b ≠ 0 repetiu les tres instruccions següents:
r ← residu de a entre b    (doneu a r el valor del residu de a entre b)      
a ← b    (el nou valor de a és l'antic valor de b)
b ← r    (el nou valor de b és el valor de r)
  • el resultat és a (el seu últim valor).

Aquest algorisme dona com a resultat 0 si a i b són nuls, mentre que en matemàtiques el major divisor de zero no existeix.

  1. ↑ Heath, Thomas Little, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
  2. ↑ Corbalán Yuste, F. et al.. Gamma 2 : matemàtiques : Educació Secundària, segon curs. 1a.. Barcelona: Vicens Vives, 2003, p. 11. ISBN 84-316-6978-2. 

Developed by StudentB