Algoritmo di Euclide

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

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 a ⇐ b e b ⇐ r 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 soltanto utilizzando l’istruzione GOTO.

Con qualche modifica (le due assegnazioni vengono eseguite comunque) può essere adattato alla esigenze della programmazione strutturata.

Function euclide(a, b: Integer): Integer;
Var
    r: Integer;
Begin
    If(b = 0) Then
        euclide:=a
    Else
        Begin
            Repeat
                r:=a Mod b;
                a:=b;
                b:=r;
            Until(r = 0);
            euclide:=a;
        End;
End;

Con qualche altra modifica si semplifica ulteriormente il codice necessario

Dati due numeri naturali a e b

Esempio

Con a=70, b=15

MCD(70, 15)=5.

Function euclide(a, b: Integer): Integer;
Var
   r: Integer;
Begin
   While(b <> 0) Then
      Begin
         r:=a Mod b;
         a:=b;
         b:=r;
      End;
   euclide:=a;
End;

Versione ricorsiva

Con a=70, b=15

Function euclide(a, b: Integer): Integer;
Begin
   If(b <> 0) Then
      euclide:=euclide(b, a Mod b)
   Else
      euclide:=a;
End;

oppure…

Function euclide(a, b: Integer): Integer;
Begin
   If(b = 0) Then
      euclide:=a
   Else
      euclide:=euclide(b, a Mod b);
End;