Algoritmo euclideo

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
cippo90
Messaggi: 23
Iscritto il: 15 lug 2006, 10:29
Località: Roè Volciano (Bs)

Algoritmo euclideo

Messaggio da cippo90 »

Scusate, ma sono ancora qui a chiedervi spiegazioni...
Cosa è l'algoritmo euclideo?
"Lasciate ogne speranza, voi ch'entrate."
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio 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.
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Avatar utente
cippo90
Messaggi: 23
Iscritto il: 15 lug 2006, 10:29
Località: Roè Volciano (Bs)

Messaggio 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???????? :?:
"Lasciate ogne speranza, voi ch'entrate."
EvaristeG
Site Admin
Messaggi: 4896
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio 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!!)
Avatar utente
luca88
Messaggi: 161
Iscritto il: 01 gen 1970, 01:00
Località: ciomp ciomp

Messaggio 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.
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio 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...
Avatar utente
cippo90
Messaggi: 23
Iscritto il: 15 lug 2006, 10:29
Località: Roè Volciano (Bs)

Messaggio da cippo90 »

Grazie mille a tutti!!!!! :wink:
"Lasciate ogne speranza, voi ch'entrate."
Rispondi