Discussione:Algoritmo di Euclide

Ho tradotto l'articolo sull'algoritmo euclideo dalla pagina omologa sulla wikipedia inglese. Lascio in questo commento la pagina originale (che era classificata come stub e come "da controllare" perche' non chiaro per chi non sa gia' di cosa si parla).

---

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun divisore tra due numeri.

Il concetto su cui si basa è semplice: il MCD tra due numeri A e B è uguale all'ultimo resto diverso da zero frutto dell'algoritmo di Euclide.

Tramite iterazioni possiamo effettuare una dimostrazione di quanto sopra enunciato se $\exists m\,>\,n\$

$m=n*q_{1}+r_{1}$ dove $q_{1}$ è il quoziente della divisione m/n

$n=r_{1}*q_{2}+r_{2}$ dove $q_{2}$ è il quoz. della divisione $n/r_{1}$

$r_{1}=r_{2}*q_{3}+r_{3}$ dove $q_{3}$ è il quoz. della divisione $r_{1}/r_{2}$

e così via fino a ricavare

$r_{n-2}=r_{n-1}*q_{n}+r_{n}$ dove $q_{n}$ è il quoz. della divisione $r_{n-2}/r_{n-1}$

$r_{n-1}=r_{n}*q_{n+1}+0$

Arrivato a questo punto il M.C.D(m,n) è pari al resto $r_{n}$ poiché ultimo resto diverso da zero.

Per esempio, calcoliamo il MCD tra 824 e 376 con il procedimento descritto prima.

MCD(824; 376) =>

                824 = 376 *2 + 72
                376 = 72  *5 + 16
                 72 = 16  *4 + 8
                 16 = 8   *2 + 0 
           

Quindi il MCD(824,76) = 8

Quando il risultato è 1, i due numeri di partenza sono coprimi.

---

--zar-(dimmi) 23:01, 27 dic 2005 (CET)

Pseudocodice

Lo pseudocodice con cui viene descritto l'algoritmo all'inizio non è di facile comprensione per tutti visto che è 1) in inglese e 2) presuppone la conoscenza di comandi specifici (anche se elementari) dei linguaggi di programmazione. Secondo me andrebbe riformulato in modo tale che anche chi non sa niente di informatica possa capire che deve fare.--Pokipsy76 09:34, 24 mar 2006 (CET)

Credo che sia abbastanza intuitivo, però non ci sono problemi a riscriverlo in pseudocodice più chiaro. Ci sono standard da rispettare scritti da qualche parte? Giusto per dare nomi "ufficiali" alle varie istruzioni (mi riferisco in particolare al while, come si traduce di solito?). --zar-(dimmi) 22:39, 24 mar 2006 (CET)

Nessuno standard, però bisogna essere comprensibili anche per chi non sa l'informatica. Una possibilità può essere questa:

1. Controlla se a = b, in tal caso l'algoritmo termina 
   e il risultato cercato è a (o b)
2. Se a ≠ b ci sono 2 possibilità:
             * a > b : in tal caso poniamo a:=a-b
             * a < b : in tal caso poniamo b:=b-a
3. Torna al punto 1.

--Pokipsy76 10:03, 25 mar 2006 (CET)

Non mi piace il "goto" :-). Mi piacerebbe replicare il ciclo while in italiano... --zar-(dimmi) 10:30, 25 mar 2006 (CET)

C'ho provato a tradurlo tenendo il ciclo while ma mi pare che se uno vuole spiegarlo per bene finisce per diventare contorto.--Pokipsy76 13:04, 25 mar 2006 (CET)

Vabbè, mettiamo quello che hai scritto tu e poi, se a qualcuno viene in mente una traduzione migliore, la farà. --zar-(dimmi) 23:17, 26 mar 2006 (CEST)