Calcolo del MCD con l'Algoritmo di Euclide
Salve, mi accingevo a fare qualche esercizio sul calcolo del MCD utilizzando l'algoritmo di Euclide (riguardo al corso di Matematica Discreta).
Se voglio calcolare il MCD tra un numero "a" ed un altro "b" entrambi diversi da 0, devo impostare la divisione euclidea di "a" per "b", impostando perciò tale formula:
a = bq + r
Come posso trovare velocemente "q" ed "r"? Il metodo più semplice (ma molto lungo, soprattutto senza calcolatrice) è quello di "andare a tentativi" moltiplicando "b" per un numero via via crescente, fino a quando non trovo un prodotto minore di "a", che sottratto ad "a" stesso mi da il resto "r". Esiste un metodo più veloce e non "a tentativi"? Con questo metodo ci metto anni per calcolare il MCD!
Scusate per la domanda che può sembrare un po' banale e forse anche stupida, ma davvero, non so che metodo usare.
Se voglio calcolare il MCD tra un numero "a" ed un altro "b" entrambi diversi da 0, devo impostare la divisione euclidea di "a" per "b", impostando perciò tale formula:
a = bq + r
Come posso trovare velocemente "q" ed "r"? Il metodo più semplice (ma molto lungo, soprattutto senza calcolatrice) è quello di "andare a tentativi" moltiplicando "b" per un numero via via crescente, fino a quando non trovo un prodotto minore di "a", che sottratto ad "a" stesso mi da il resto "r". Esiste un metodo più veloce e non "a tentativi"? Con questo metodo ci metto anni per calcolare il MCD!
Scusate per la domanda che può sembrare un po' banale e forse anche stupida, ma davvero, non so che metodo usare.
Risposte
"Omar_93":
Salve, mi accingevo a fare qualche esercizio sul calcolo del MCD utilizzando l'algoritmo di Euclide (riguardo al corso di Matematica Discreta).
Se voglio calcolare il MCD tra un numero "a" ed un altro "b" entrambi diversi da 0, devo impostare la divisione euclidea di "a" per "b", impostando perciò tale formula:
a = bq + r
Come posso trovare velocemente "q" ed "r"? Il metodo più semplice (ma molto lungo, soprattutto senza calcolatrice) è quello di "andare a tentativi" moltiplicando "b" per un numero via via crescente, fino a quando non trovo un prodotto minore di "a", che sottratto ad "a" stesso mi da il resto "r". Esiste un metodo più veloce e non "a tentativi"? Con questo metodo ci metto anni per calcolare il MCD!
Scusate per la domanda che può sembrare un po' banale e forse anche stupida, ma davvero, non so che metodo usare.
La divisione con resto la sai fare? è semplicemente questa.
Esempio :
$4/3 = 3*1+1$ ove $q=1 , r=1$
"Kashaman":
La divisione con resto la sai fare? è semplicemente questa.
Esempio :
$4/3 = 3*1+1$ ove $q=1 , r=1$
Se devo fare il MCD di due numeri grandi, come 2182 e 147, imposto la formula:
$2182 = 147*q + r$
E in questo caso trovare q non è così semplice, dovrei provare a moltiplicare 147 per numeri crescenti fino a trovare che q è 14 ed r è 124, ma se mi capitano numeri ancor più grandi ci metto sempre più tempo. Mi chiedevo se ci fosse qualche metodo più veloce.
Non per offendere ma devi fare la normale divisione in colonna http://didatticamatematicaprimaria.blog ... terza.html Non li provi certo tutti...
"vict85":
Non per offendere ma devi fare la normale divisione in colonna http://didatticamatematicaprimaria.blog ... terza.html Non li provi certo tutti...
Ottimo, mi chiedevo se ci fosse un metodo alternativo, ovviamente la divisione così la so fare.
Puoi vedere in questa pagina http://en.wikipedia.org/wiki/Division_algorithm ma penso sia più che altro fatti per pc...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo