DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come affrontare un
problema…
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 24 Agosto 2015
Massimo Comune Divisore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Definizione
 Dicesi Massimo Comune Divisore (M.C.D.)
il piu’ grande tra i divisori comuni a due o
piu’ numeri
• Il nostro problema:
 Dati due numeri interi, si trovi il MCD
2
Parte 0/4: La brutta notizia!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Abbiamo un problema!!!!
 Dati due numeri interi, si trovi il MCD
how to solve it di Poyla G. - http://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.pdf
3
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 1/4: Capire il problema
 Quale e’ il problema generale che si scerca
di risolvere?
4
Parte 1/4: Capire il problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Abbiamo un solo problema?
 Dati due numeri interi, si trovi il MCD
• P1: Ci servono due numeri interi
• P2: Dobbiamo trovare il MCD di due
numeri
5
Abbiamo solo P1 e P2?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dati due numeri interi, si trovi il MCD
• P1: Ci servono due numeri interi
 P1.1: Ci servono due scatole per salvare i due numeri
 P1.2: I numeri devono essere maggiori uguali a 1
• P2: Dobbiamo trovare il MCD di due numeri
 P2.1: Dobbiamo trovare tutti i divisori di un numero (X)
 P2.2: Dobbiamo trovare tutti i numeri {C} in comune a due
sequenze {S1, S2} di numeri
 P2.3: Dobbiamo trovare il maggiore tra N numeri
6
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•Parte 2/4: Fare/creare un piano
 Ci possono essere diverse strategie per
risolvere lo stesso problema
•
•
•
•
Ipotizzare e verificare
Cercare dei pattern
Risolvere problemi più piccoli
Disegnare uno schema
7
Parte 2/4: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dati due numeri interi, si trovi il MCD
• P1: Ci servono due numeri interi
 P1.1: Ci servono due scatole per salvare i due numeri
 P1.2: I numeri devono essere maggiori uguali a 1
• P2: Dobbiamo trovare il MCD di due numeri
 P2.1: Dobbiamo trovare tutti i divisori di un numero (X)
 P2.2: Dobbiamo trovare tutti i numeri {C} in comune a due
sequenze {S1, S2} di numeri
 P2.3: Dobbiamo trovare il maggiore tra N numeri
8
P1: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P1: Ci servono due numeri interi
 P1.1: Ci servono due scatole per salvare i
due numeri
• Di che tipo sono i numeri che ci servono?
 P1.2: I numeri devono essere maggiori
uguali A 1
• Come facciamo a garantire che il numero
inserito sia maggiore uguale a 1?
9
P1.2: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P1.2: I numeri devono essere maggiori
uguale a 1
 Come facciamo a garantire che il numero
inserito sia maggiore uguale a 1?
A. Inserisci il numero
B. Il numero è maggiore o uguale a 1
a. Se si FINE
b. Se no, torna a A
10
P1.2: Chiariamo meglio…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P1.2: I numeri devono essere maggiori
uguale a 1
 Come facciamo a garantire che il numero
inserito sia maggiore uguale a 1?
A. Inserisci il numero
B. Finché Il numero è minore di 1, torna ad A
11
P1.1+P1.2: P1 risolto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. P1.1: Leggo un dato intero N1
2. P1.2: Finché N1 è minore di 1, torna
ad 1
3. P1.1: Leggo un dato intero N2
4. P1.2: Finché N2 è minore di 1, torna
ad 3
12
P2: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2: Dobbiamo trovare il MCD di due
numeri
 P2.1: Dobbiamo trovare tutti i divisori di un
numero (X)
 P2.2: Dobbiamo trovare tutti i numeri {C} in
comune a due sequenze {S1, S2} di numeri
 P2.3: Dobbiamo trovare il maggiore tra N
numeri
13
P2.1: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.1: Dobbiamo trovare tutti i divisori di
un numero (X)
 Definisco D come numero che varia tra 1 e
X
• Dati X e D, interi positivi
• se X/D da resto 0,
– D è divisore di X
14
P2.2: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.2: Dobbiamo trovare tutti i numeri {C}
in comune a due sequenze {S1, S2} di
numeri
 Dato X1 appartenente a S1
 Dato X2 appartenente a S2
 Se X1 è uguale a X2 allora il valore è comune
a S1 e S2
15
P2.3: Chiariamo meglio…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.3: Dobbiamo trovare il maggiore tra N
numeri
1. Il maggiore è il primo numero di N
2. Vi è un altro numero in N?
A. Si
a.
b.
c.
d.
Confronto il maggiore con il successivo
Il successivo è maggiore?
Si: il maggiore diventa il successivo
Vado a 2
B. No: vado a 3
3. Il maggiore è maggiore
16
P2.3: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.3: Dobbiamo trovare il maggiore tra N
numeri
1. Il maggiore è il primo numero di N
2. Finché vi sono numeri in N?
a.
b.
c.
d.
Confronto il maggiore con il successivo
Il successivo è maggiore?
Si: il maggiore diventa il successivo
Vado a 2
3. Il maggiore è maggiore
17
P2.1+P2.2: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.1: Dobbiamo trovare tutti i divisori di un
numero
• P2.2: Dobbiamo trovare tutti i numeri {C}
in comune a due sequenze {S1, S2} di
numeri
Come sono i numeri in {C}? (P2.2)
Sono divisori di un numero! (P1.1)
18
P2.1+P2.2: Ricordiamo…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.1: Dobbiamo trovare tutti i divisori di un
numero (X)
 Definisco D come numero che varia tra 1 e X
• Dati X e D, interi positivi
• se X/D da resto 0, D è divisore di X
• P2.2: Dobbiamo trovare tutti i numeri {C} in
comune a due sequenze {S1, S2} di numeri
 Dato D1 appartenente a S1
 Dato D2 appartenente a S2
 Se D1 è uguale a D2 allora il valoro è comune a S1 e
S2
19
P2.1+P2.2: ma quindi…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• P2.1: D1 divide N1 (appartiene a S1)
• P2.1: D2 divide N2 (appartiene a S2)
• P2.2: D1 è uguale a D2?
 SI: D1 (o D2) è un divisore comune a N1 e a
N2
Se D1 è maggiore di N2?
Se D2 è maggiore di N1?
20
P2.1+P2.2: e ancora…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• X=1
• Finché X è minore o uguale a N1 e a N2
 P2.1: X divide N1? e X divide N2?
• SI: P2.2 X è divisore comune a N1 e a N2
 Incremento X
E cosa facciamo a P2.3?
21
P2.3: Fare/creare un piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.3: Dobbiamo trovare il maggiore tra N
numeri
1. Il maggiore è il primo numero di N
2. Finché vi sono numeri in N?
a.
b.
c.
d.
Confronto il maggiore con il successivo
Il successivo è maggiore?
Si: il maggiore diventa il successivo
Vado a 2
3. Il maggiore è maggiore
E se gli N numeri fossero ordinati
in ordine crescente?
22
P2.3: Numeri ordinati
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• P2.3: Dobbiamo trovare il maggiore tra N
numeri
1. Il maggiore è l’ultimo numero di N
Essendo ordinati in ordine crescente
Ogni successero è maggiore del precedente
Come usiamo questa idea?
23
P2.1+P2.2+P2.3
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• X=1
• Finché X è minore o uguale a N1 e a N2
 P2.1: X divide N1? e X divide N2?
• SI: P2.2 X è divisore comune a N1 e a N2
 Incremento X
P2.3: Dobbiamo trovare il maggiore tra N
numeri
Come varia X? In ordine crescente :)
24
P2: risolto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• X = 1 e TMP = 1
• Finché X è minore o uguale a N1 e a N2
 P2.1: X divide N1? e X divide N2?
• SI:
– P2.2: X è divisore comune a N1 e a N2
– P2.3: TMP = X
 Incremento X
• TMP è il MCD
25
P1 + P2: mettiamo tutto insieme
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
2.
3.
4.
5.
6.
P1.1: Leggo un dato intero N1
P1.2: Finché N1 è minore di 1, torna ad 1
P1.1: Leggo un dato intero N2
P1.2: Finché N2 è minore di 1, torna ad 3
X = 1 e TMP = 1
Finché X è minore o uguale a N1 e a N2
1. P2.1: X divide N1? e X divide N2?
1. SI:
1.
2.
P2.2: X è divisore comune a N1 e a N2
P2.3: TMP = X
2. Incremento X
7. TMP è il MCD
26
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 3/4: Portare avanti il piano
 Mettere in azione il vostro piano!
 Rimanere sul piano deciso a meno che
non vi siano evidenti motivi per credere
che esso non funzionerà più
La pazienza è il vostro miglior alleato
27
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Quante e quali variabili ci servono?
1.
2.
3.
4.
5.
6.
P1.1: Leggo un dato intero N1
P1.2: Finché N1 è minore di 1, torna ad 1
P1.1: Leggo un dato intero N2
P1.2: Finché N2 è minore di 1, torna ad 3
X = 1 e TMP = 1
Finché X è minore o uguale a N1 e a N2
1.
P2.1: X divide N1? e X divide N2?
1.
SI:
1.
2.
2.
7.
P2.2: X è divisore comune a N1 e a N2
P2.3: TMP = X
Incremento X
TMP è il MCD
28
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Quante e quali variabili ci servono?
29
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. P1.1: Leggo un dato intero N1
2. P1.2: Finché N1 è minore di 1, torna
ad 1
30
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
5. X = 1 e TMP = 1;
31
Definisco la condizione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
6. Finché X è minore o uguale a N1 e a N2
A: X <= N1
B: X <= N2
A B
0 0
0 1
1 0
1 1
uscita
0
0
0
1
6. Finché ((X<=N1) AND (X<=N2))
32
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
6. Finché X è minore o uguale a N1 e a N2
1. P2.1: X divide N1? e X divide N2?
1. SI:
1.
2.
P2.2: X è divisore comune a N1 e a N2
P2.3: TMP = X
2. Incremento X
33
Funzioni equivalenti 1
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A: N1%X
B: 0
A B
0 0
!0 0
uscita
0
1
uscita è identica ad A
uscita = A
NO!!!!!
34
Vediamo il codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
35
Vediamo il codice: debug
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
36
Vediamo il codice: debug
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
37
Funzioni equivalenti 1: corretta
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A: N1%X
B: 0
A B
0 0
!0 0
uscita
1
0
uscita è identica all’inverso di A
uscita = !A
38
Funzioni equivalenti 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
è equivalente a
39
Parte 3/4: Portare avanti il piano
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
2.
3.
4.
5.
6.
P1.1: Leggo un dato intero N1
P1.2: Finché N1 è minore di 1, torna ad 1
P1.1: Leggo un dato intero N2
P1.2: Finché N2 è minore di 1, torna ad 3
X = 1 e TMP = 1;
Finché X è minore o uguale a N1 e a N2
1. P2.1: X divide N1? e X divide N2?
1. SI:
1.
2.
P2.2: X è divisore comune a N1 e a N2
P2.3: TMP = X
2. Incremento X
7. TMP è il MCD
40
MCD: Finito…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
41
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 4/4: Ragionare e comprendere
 Comprendere quello che si è fatto e dove
l’algoritmo individuato possa essere
applicato al meglio
La pratica è fondamentale!
42
Ma scusate…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
N1 = 200000
N2 = 100000
Vogliamo veramente partire da 1
Finché ((X<=N1) AND (X<=N2))
??????
43
P2: risolto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• X = 1 e TMP = 1
• Finché X è minore o uguale a N1 e a N2
 P2.1: X divide N1? e X divide N2?
• SI:
– P2.2: X è divisore comune a N1 e a N2
– P2.3: TMP = X
 Incremento X
• TMP è il MCD
44
Tornado nel passato…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
45
P2: risolto
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dati due numeri N1 e N2
• X = min (N1,N2)
• Finché P2.1: X non divide N1 e N2
 Decremento X
• P2.2 e P2.3: X è divisore comune a N1 e a
N2
46
Definisco la condizione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Finché X non divide N1 e N2
A: N1%X
B: N2%X
A B
0 0
0 1
1 0
1 1
uscita
1
0
0
0
Finché !(!(N1%x) AND !(N2%X))
47
Definisco la condizione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
A
0
0
1
1
B
0
1
0
0
!A
1
1
0
0
!B (!A && !B) !(!A && !B)
1
1
0
0
0
1
1
0
1
1
0
1
Continuo
finché 1
48
MCD: Finito!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
49