Scusate, ma sono ancora qui a chiedervi spiegazioni...
Cosa è l'algoritmo euclideo?
Algoritmo euclideo
Algoritmo euclideo
"Lasciate ogne speranza, voi ch'entrate."
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.
Piccolo suggerimento, prima di domandare da' un'occhiata ai vecchi post di questa sezione, e solo se non trovi niente chiedi.
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
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:Piccolo suggerimento, prima di domandare da' un'occhiata ai vecchi post di questa sezione, e solo se non trovi niente chiedi.
Come si usa l'algoritmo euclideo????????
"Lasciate ogne speranza, voi ch'entrate."
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!!)
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!!)
sappi che, se $ a>b $ allora $ MCD(a,b)=MCD(b,a-b) $ e così via. Che poi è come usare l'algoritrmo euclideo.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...
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...
