Tag Archives: Euclide

Algoritmo di Euclide

L’algoritmo di Euclide permette di calcolare il massimo comun divisore, MCD, tra due numeri interi.


Algoritmo

Dati due numeri naturali a e b

  • se b è zero allora la risposta è a
  • altrimenti si divide a per b e si assegna ad r il resto della divisione
    • se r=0 allora la risposta è b
    • altrimenti ab e br e si ripete nuovamente la divisione.

Esempi

Con a=70, b=15

MCD(70, 15)=5

Con a=15, b=70

MCD(15, 70)=5

Con a=71, b=15

MCD(71, 15)=1.



L’algoritmo precedente può essere trasformato in un programma di alto livello dopo qualche modifica per adattarlo alla esigenze della programmazione strutturata.

Dati due numeri naturali a e b

mentre b è diverso da 0 ripeti

  • r ⇐ resto della divisione intera tra a e b
  • ab
  • br

la risposta è a



Versione ricorsiva


Codifica: Python


Wikipedia: Algoritmo di Euclide