Pagina 1 di 1

Algoritmo euclideo

Inviato: 02 ago 2006, 20:46
da cippo90
Scusate, ma sono ancora qui a chiedervi spiegazioni...
Cosa è l'algoritmo euclideo?

Inviato: 03 ago 2006, 07:13
da Sisifo
E' l'algoritmo per il calcolo del Masssimo Comun Divisore..

Piccolo suggerimento, prima di domandare da' un'occhiata ai vecchi post di questa sezione, e solo se non trovi niente chiedi.

Inviato: 08 ago 2006, 12:17
da cippo90
Piccolo suggerimento, prima di domandare da' un'occhiata ai vecchi post di questa sezione, e solo se non trovi niente chiedi.
Ho seguito il tuo consiglio, Sisifo, ma non ho trovato niente che mi spieghi in che cosa consiste o come si utilizza, quindi, dopo aver cercato con cura, chiedo:
Come si usa l'algoritmo euclideo???????? :?:

Inviato: 08 ago 2006, 14:43
da EvaristeG
In effetti è probabile che nessuno ne abbia mai parlato ... se anche è già successo, repetita iuvant.

Allora, innanzitutto, chiamiamo divisione euclidea l'operazione che, a due numeri interi $ a > b $ associa altri due numeri interi $ q,r $ con $ 0\leq r\leq b-1 $ tali che
$ a=b\cdot q + r $
Insomma, la solita divisione con resto ... interessante notare che, con le condizioni imposte su r, la coppia (q,r) è unica.

L'algoritmo euclideo è un procedimento per trovare il massimo comun divisore tra due numeri interi (il più grande tra i divisori comuni). Supponiamo di voler calcolare m=MCD(a,b); supponiamo $ a\geq b $ e facciamo la divisione euclidea tra loro
$ a=bq_1+r_1 $
ora, se $ r_1=0 $, allora $ MCD(a,b)=b $, altrimenti $ MCD(a,b)=MCD(b,r_1) $ (se un numero divide a e b, divide anche il resto, se invece divide il resto e b, divide anche a); quindi rifacciamo la divisione euclidea tra b e il resto :
$ b=r_1q_2+r_2 $
se $ r_2=0 $, allora $ MCD(a,b)= $$ MCD(b,r_1)=r_1 $, altrimenti $ MCD(b,r_1)=MCD(r_1,r_2) $.
Proseguiamo facendo successive divisioni finchè non si ottiene resto nullo, ottenendo la sequenza :
$ a=bq_1+r_1 $

$ b=r_1q_2+r_2 $
$ r_1=r_2q_3+r_3 $
$ \ldots $
$ r_{n-1}=r_nq_{n+1} $
e si avrà $ MCD(a,b)=MCD(b,r_1)= $$ MCD(r_1,r_2)=\ldots=MCD(r_{n-1},r_n)=r_n $
Quindi l'ultimo resto non nullo ottenuto è il massimo comun divisore tra a e b.

Invertendo questo procedimento, risalendo la catena di divisioni, si riescono a trovare due numeri interi s,t tali che
$ MCD(a,b)=r_n=s\cdot a+t\cdot b $
(uguaglianza nota come teorema di Bezout).

(Consiglio : fatti degli esempi!!)

Inviato: 08 ago 2006, 15:13
da luca88
Per il calcolo del massimo comun divisore, se i numeri non son troppo grandi, o se sei veloce a fare i calcoli :D sappi che, se $ a>b $ allora $ MCD(a,b)=MCD(b,a-b) $ e così via. Che poi è come usare l'algoritrmo euclideo.

Inviato: 08 ago 2006, 15:19
da ma_go
per inciso...
l'algoritmo euclideo si applica tale e quale anche in altre situazioni (in quelli che si chiamano, guarda caso, anelli euclidei o domini euclidei, ma queste sono cose che non si dovrebbero dire in un forum olimpico)...
a livello olimpico, credo che l'unica altra applicazione sia ai polinomi, comunque: per trovare l'MCD tra due polinomi usi esattamente lo stesso algoritmo che usi per i numeri interi, e funziona tutto come dovrebbe...

Inviato: 08 ago 2006, 18:44
da cippo90
Grazie mille a tutti!!!!! :wink: