Implementazioni di algoritmi/Algoritmo di Euclide: differenze tra le versioni
Ottimizzato codice VB.NET |
Nessun oggetto della modifica |
||
Riga 4: | Riga 4: | ||
Dati due numeri naturali a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche espresso in modo naturale utilizzando la '''ricorsione in coda'''. |
Dati due numeri naturali a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche espresso in modo naturale utilizzando la '''ricorsione in coda'''. |
||
== Implementazioni == |
|||
=== Implementazione in [[C]]/[[C++]] - versione ricorsiva === |
|||
=== [[C]]/[[C++]] === |
|||
; versione ricorsiva |
|||
<source lang="c"> |
<source lang="c"> |
||
int mcd(int a, int b) { |
int mcd(int a, int b) { |
||
Riga 14: | Riga 16: | ||
</source> |
</source> |
||
; versione non ricorsiva |
|||
<source lang="c"> |
<source lang="c"> |
||
int mcd(int a, int b) { |
int mcd(int a, int b) { |
||
Riga 26: | Riga 28: | ||
} |
} |
||
</source> |
</source> |
||
=== Implementazione in [[Python]] - versione ricorsiva === |
|||
=== [[Python]] === |
|||
; versione ricorsiva |
|||
<source lang="python"> |
<source lang="python"> |
||
def mcd(a,b): |
def mcd(a,b): |
||
Riga 34: | Riga 38: | ||
return mcd(b,(a%b)) |
return mcd(b,(a%b)) |
||
</source> |
</source> |
||
=== Implementazione in [[Python]] - versione non ricorsiva === |
|||
; versione non ricorsiva |
|||
<source lang="python"> |
<source lang="python"> |
||
def mcd(a, b): |
def mcd(a, b): |
||
Riga 41: | Riga 46: | ||
return a |
return a |
||
</source> |
</source> |
||
⚫ | |||
=== [[MATLAB]]/Octave === |
|||
; versione ricorsiva |
|||
<source lang="MATLAB"> |
|||
function val = mcd(a, b): |
|||
if b == 0 |
|||
val = a; |
|||
else |
|||
val = mcd(b, rem(a,b)) |
|||
end |
|||
</source> |
|||
; versione non ricorsiva |
|||
<source lang="MATLAB"> |
|||
function val = mcd(a, b): |
|||
if b == 0 |
|||
val = a; |
|||
else |
|||
temp = a; |
|||
a = b; |
|||
b = rem(temp,b); |
|||
end |
|||
</source> |
|||
⚫ | |||
; versione non ricorsiva |
|||
<source lang="vb"> |
<source lang="vb"> |
||
Function MCD(ByVal a As Integer, ByVal b As Integer) As Integer |
Function MCD(ByVal a As Integer, ByVal b As Integer) As Integer |
||
Riga 53: | Riga 83: | ||
End Function |
End Function |
||
</source> |
</source> |
||
[[Categoria:Implementazioni di algoritmi|Algoritmo di Euclide]] |
[[Categoria:Implementazioni di algoritmi|Algoritmo di Euclide]] |
||
Versione delle 16:07, 21 set 2014
L'algoritmo di Euclide è un algoritmo per trovare il massimo comun divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia l'algoritmo non è stato probabilmente scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi.
Dati due numeri naturali a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche espresso in modo naturale utilizzando la ricorsione in coda.
Implementazioni
C/C++
- versione ricorsiva
int mcd(int a, int b) {
if (b == 0)
return a;
else
return mcd(b, a % b);
}
- versione non ricorsiva
int mcd(int a, int b) {
int t;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
Python
- versione ricorsiva
def mcd(a,b):
if b==0:
return a
else:
return mcd(b,(a%b))
- versione non ricorsiva
def mcd(a, b):
while b:
a, b = b, a%b
return a
MATLAB/Octave
- versione ricorsiva
function val = mcd(a, b):
if b == 0
val = a;
else
val = mcd(b, rem(a,b))
end
- versione non ricorsiva
function val = mcd(a, b):
if b == 0
val = a;
else
temp = a;
a = b;
b = rem(temp,b);
end
Visual Basic .NET
- versione non ricorsiva
Function MCD(ByVal a As Integer, ByVal b As Integer) As Integer
Dim m As Decimal
While b <> 0
m = a Mod b
a = b
b = m
End While
Return a
End Function