Algoritmo di Euclide: differenze tra le versioni

Versione delle 14:29, 18 set 2021

Versione attuale delle 13:09, 1 mag 2025

(21 versioni intermedie di 18 utenti non mostrate)

Riga 1:

L''''algoritmo di Euclide''' è un [[algoritmo]] per trovare il [[massimo comun divisore|massimo comune divisore]] (indicato di seguito con MCD) tra due [[numero intero|numeri interi]]. È uno degli algoritmi più antichi conosciuti, essendo presente negli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]]<ref>F. Acerbi, ''Euclide, Tutte le opere'', 2007, [[Bompiani]].

{{en}} [[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> intorno al [[300 a.C.]]; tuttavia, probabilmente l'algoritmo non è stato 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 (Aristotele)Topici|I topici]]'', 158b, 29-35. L'algoritmo non richiede la [[fattorizzazione]] dei due interi.

Dati due [[numero naturale|numeri naturali]] <math>a</math> e <math>b</math>, l'algoritmo prevede che si controlli se <math>b</math> è zero (questa prima fase rientra ovviamente nell'ambito di un uso moderno dell'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano il concetto di zero). Se lo è, <math>a</math> è il MCD. Se non lo è, si

deve dividere <math>\frac{a}{b}</math> e definire <math>r</math> come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se <math>r=0</math> allora si può affermandoaffermare che <math>b</math> è il MCD cercato, altrimenti occorre assegnare <math>a'=b</math> e <math>b'=r</math> e ripetere nuovamente la divisione.

L'algoritmo può essere espresso in modo naturale utilizzando la [[Algoritmo ricorsivo#Ricorsione in coda|ricorsione in coda]].

Riga 10:

Questo è noto con il nome di [[Algoritmo esteso di Euclide|algoritmo di Euclide esteso]].

Questi algoritmi possono essere usati, oltre che con i [[numeri interi]], in ogni contesto in cui è possibile eseguire lal'operazione di divisione colcon resto. Ad esempio, l'algoritmo funziona per i [[polinomio|polinomi]] ad una indeterminata su un [[campo (matematica)|campo]] ''K'', o polinomi omogenei a due indeterminate su un campo, o gli [[intero gaussiano|interi gaussiani]]. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato [[anello euclideo]].

Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra.

== Pseudocodice ==

Una scrittura in [[pseudocodice]] dell'algoritmo (in cui «mod» indica il resto della divisione intera) è la seguente<ref>{{Cita web|url=https://www.treccani.it/enciclopedia/algoritmo-di-euclide_(Enciclopedia-della-Matematica)/|titolo=Euclide, algoritmo di - Treccani|sito=Treccani|lingua=it|accesso=2023-12-27}}</ref>:

inizia

Whileleggi (r <>a, 0b)

while finché b !=> 0 fai:

r <- mod(a =, b)

a <- b = r

End Whileb <- r

fine ciclo

scrivi (a, "è il massimo comun divisore cercato")

finisci.

==Dimostrazione della correttezza dell'algoritmo==

Riga 39 ⟶ 52:

==Codici==

{{C|Controllare se i codici vanno mantenuti o trasferiti ad un altro progetto|informatica|giugno 2015}}

[[C (linguaggio di programmazione)|C]] e [[C++]] (algoritmo iterativo)

<syntaxhighlight lang="c" line="1">

/* Algoritmo iterativo */

int Euclide(int a, int b) // prototipo della funzione Euclide //

int euclide(int a, int b)

{

int r; // resto della divisione

while(b != 0) //ripetereripete finché non riduciamoriduce b a zero

{

r = a % b; // in r salva il resto della divisione tra a e b

a = b; // scambia il ruolo di a e b

b = r; //scambiamo ilin ruolob diora c'è r = a e% b

}

return a; //... e quando b è (o è diventato) 0, il risultato è in a

}

</syntaxhighlight>

[[C (linguaggio)|C]] e [[C++]] (algoritmo ricorsivo)
<syntaxhighlight lang="c" line="1">

/* Algoritmo ricorsivo */

/*ALGORITMO RICORSIVO*/

int gcdeuclide(int ma, int nb)
{

if(nb == 0)

return(ma);

else

return gcdeuclide(nb, ma %n b); // la funzione richiama sé stessa

}

</syntaxhighlight>

[[Scala (linguaggio di programmazione)|Scala]] (algoritmo ricorsivo)
<syntaxhighlight lang="scala" line="1">

@tailrec

def gcdeuclide(ma: Int, nb: Int): Int =

if (nb == 0)

ma

else

gcdeuclide(nb, ma % nb)

</syntaxhighlight>

[[MATLAB]] (algoritmo iterativo)

<syntaxhighlight lang="matlab" line="1">

function out = miogdc euclide(a, b)

if(b == 0)

out = a;

elseif(b == 1)

out = 1;

else

out = miogdceuclide(b, mod(a,b));

end

Riga 89 ⟶ 104:

</syntaxhighlight>

[[Python]] (algoritmo iterativo)

<syntaxhighlight lang="Pythonpython" line="1">

def MCDeuclide(a, b):

<syntaxhighlight lang="Python">

while }b:

def MCD(a,b):

while b != 0:

a, b = b, a % b

return a

</syntaxhighlight>

[[Ruby (linguaggio di programmazione)|Ruby]] (algoritmo iterativo)

<syntaxhighlight lang="ruby" line="1">

<syntaxhighlight lang="ruby">

def euclide(a, b)

while( b != 0) do

a, b = b, a % b

end

return a

end

</syntaxhighlight>

[[Pascal (linguaggio di programmazione)|Pascal]] (algoritmo iterativo)

<syntaxhighlight lang="Pascalpascal" line="1">

function MCDeuclide(a, b: integer): integer;

var
r: integer;

begin

if b = 0 then

MCD := a

else begin

r:=(a mod b);begin

while not ( r := 0)(a domod b);

while not (r = a Mod0) bdo

begin

a:=b;

b a :=r b;

r:=(a mod b) := r;

Dim r As Int16 r := (a Modmod b);

end;

MCD:=b end;

ReturnMCD := b;

end;

a:=b end;

end;

</syntaxhighlight>

[[BASIC]] (vb.net, algoritmo iterativo)

<syntaxhighlight lang="vbnet" line="1">

Function Euclide_MCDEuclide(ByVal a As Int16, ByVal b As Int16) As Int16

Dim r As Int16 = a Mod b

While (r <> 0)

Function Euclide_MCD(ByVal a As Int16, ByVal b As Int16) As Int16

a = b

b = r

r = a Mod b

Wend

Return b

Dim r As Int16 = a Mod b

End Function

While (r <> 0)

a = b

b = r

r = a Mod b

End While

Return b

End Function

</syntaxhighlight>

In questo algoritmo è stato usato per la rappresentazione numerica il tipo "int16", ma può essere cambiatacambiato a piacimento con qualsiasi altro tipo di variabile numerica secondo i bisogni del programma.

[[PHP]] (algoritmo iterativo)

<syntaxhighlight lang="PHPphp" line="1">

function euclide($a, $b) {

function mcd while ($a,$b) {

while($b) list($a, $b) = array($b, $a % $b);

}

return $a;

return $a;

}

</syntaxhighlight>

[[Java (linguaggio di programmazione)|Java]] (algoritmo iterativo)

Java

<syntaxhighlight lang="java" line="1">

private static int MCDeuclide(int a, int b) {

int a, int b, int r;

while (b != 0) {

r = a % b;

a = b;

b = r;

}

return Math.abs(a);

}

}

</syntaxhighlight>

[[Rust (linguaggio di programmazione)|Rust]]<ref>{{Cita web|url=https://github.com/ProgrammingRust|titolo=Programming Rust|sito=GitHub|lingua=en|accesso=2023-01-06}}</ref> (algoritmo iterativo)

<syntaxhighlight lang="rust" line="1">

fn euclide(mut a: u64, mut b: u64) -> u64 {

assert! (a != 0 && b != 0);

while b != 0 {

let r = a % b;

a = b;

b = r;

}

a

}

</syntaxhighlight>

[[Go (linguaggio di programmazione)|Go]] (algoritmo iterativo)

<syntaxhighlight lang="go" line="1">

func euclide(a, b int) int {

for b != 0 {

a, b = b, a%b

}

return $a;

}

</syntaxhighlight>

Riga 182 ⟶ 216:

*[[Minimo comune multiplo]]

*[[Massimo comun divisore]]

*[[Algoritmo esteso di Euclide]]

*[[Equazione diofantea lineare]]

*[[Ritmo di Euclide]]

Riga 190 ⟶ 225:

==Collegamenti esterni==

* {{Collegamenti esterni}}

* {{FOLDOC|Euclid's Algorithm|Euclid's Algorithm}}

*{{en}} [https://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] su cut-the-knot

*{{en}} [https://www.cut-the-knot.org/blue/binary.shtml Binary Euclid's Algorithm (Java)] su cut-the-knot

Riga 199 ⟶ 236:

{{Portale|matematica}}

[[Categoria:Algoritmi per la matematicaaritmetici|Euclide]]

[[Categoria:Euclide]]