1

PROGRAMMARE IL MASSIMO COMUNE DIVISORE

Cosimo Laneve

2

argomenti

1. il massimo comune divisore

2. l’algoritmo della scuola e ottimizzazioni

3. il teorema di Euclide e l’algoritmo relativo

4. ottimizzazione dell’algoritmo di Euclide

5. cenni di complessità computazionale

3

algoritmo MCD/1 – MCD della scuola1. prendi due numeri m ed n;!

2. calcola i divisori (primi) di m e di n;!a)calcolo dei divisori (primi) di m: si usa una sequenza di

naturali: il primo elemento sarà l’esponente di 2, il secondo sarà l’esponente di 3, il terzo sarà l’esponente di 4, etc.; si usa un valore k che rappresenta il divisore (primo). All’inizio k = 2;!

i. x rappresenta l’esponente: x=0; !ii. calcola m/k;!! se il resto è 0 allora m = m/k e x=x+1 e !

! riesegui ii; altrimenti metti il valore di x in coda ! alla sequenza, e vai a i. con k= k+1!

iii. quando m diventa 1 il calcolo termina!

b)fare lo stesso procedimento per n !

3. sia h1·h2·...·hs la sequenza ottenuta dal calcolo dei divisori di m; sia h1’·h2’·...·ht’ la sequenza ottenuta dal calcolo dei divisori di n; sia r= min(s,t)!

4. MCD(m,n) = 2min(h1,h1’)*3min(h2,h2’)*...*(r+1)min(hr,hr’)

4

algoritmo MCD/1 – MCD della scuola/commenti

• nel calcolo dei divisori di un numero, gli unici esponenti non nulli corrisponderanno a divisori primi (non è scritto ma deriva dall’algoritmo)

• le iterazioni dell’algoritmo nel caso pessimo (m ed n sono co-primi) sono m+n+max(m,n)

• l’implementazione in C++ dell’algoritmo ha un errore… • l’algoritmo si può migliorare iterando sino a sqrt(m)

teorema: un numero m non è primo se è divisibile per numeri compresi tra 2 e sqrt(m) (estremi inclusi)

5

algoritmo MCD/2: un metodo più diretto per il MCD

1.prendi due numeri m ed n;!

2.prendere il più piccolo dei due numeri, sia esso m;!

3.sia mcd = 1!

4.si verifica che ogni numero x compreso tra 2 e il numero m sia o meno un divisore dei due numeri in input;!

5.nel caso x è un divisore, allora mcd = mcd*x e torna a 4 aggiornando m = m/x e n = n/x; altrimenti x = x+1 e torna a 4!

! // l’algoritmo termina quando x > m !

!commenti: numero di iterazioni eseguite (numeri co-primi) ! ! ≤ min(m,n)

6

algoritmo MCD/3: il Teorema di Euclide

Teorema di Euclide: se m>n allora MCD(m,n) = MCD(m-n,n)!

prova: innanzitutto si osservi che MCD(m,n) è anche un divisore di m-n: m ! = MCD(m,n)*h! n ! = MCD(m,n)*k!quindi m-n ! = MCD(m,n)*(h-k) Ora si osservi che MCD(m,n) è anche il massimo comune divisore tra m-n e n: per assurdo assumiamo che non sia il massimo, perciò esiste h’>1

k=h’*k’ e h-k = h’*h” quindi n ! ! = ! MCD(m,n)*h’*k’!! m-n! ! = ! MCD(m,n)*h’*h”!! (m-n)+n ! = ! MCD(m,n)*h’*(h”+k’) assurdo!

7

algoritmo MCD/3: l’algoritmo di Euclide1.se ! m == n ! allora ! m = mcd(m,n) !

2.se ! (m != n) ! allora !

! i. m > n allora m = m - n (perchè mcd(m,n) = mcd(m-n,n))!

! ii. m < n allora n = n - m (perchè mcd(m,n) = mcd(m,n-m))!

! iii. ritorna a 1.!

3. stampa m

commenti:

numero di iterazioni eseguite (caso pessimo uno dei due valori è 1) ≈ max(m,n)

8

algoritmo MCD/4: l’algoritmo di Euclide ottimizzato

osservazione: quando uno dei due numeri è molto più grande dell’altro, allora l’algoritmo di Euclide esegue numerosi cicli per sottrarre la quantità più piccola dal numero più grande

esempio. m = 1000, n = 2 1o iterazione: m = 1000, ! n = 2 2o iterazione: m = 998, ! n = 2 3o iterazione: m = 996, ! n = 2 . . . 499o iterazione: m = 2, ! n = 2

!soluzione più efficiente: utilizzare il resto invece della differenza!

esempio: m = 1000, n = 2 1o iterazione: m = 1000, n = 2

2o iterazione: m = 2 (perchè 1000%n == 0), n = 2

9

b

1. se n>m allora r = n altrimenti r = m; m = n ; n = r ;!

2. se ! (r != 0) ! allora!

a) r = m % n ;!

b) m = n ; !

c) n = r ;!

d) ritorna a 2!

3.!stampa m ! !

commenti: numero di iterazioni eseguite (caso pessimo) ≈ log2(max(m,n))

perchè m % n <= m/2