DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Come affrontare un problema… Marco D. Santambrogio –...

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Come affrontare un Come affrontare un problema…problema…

Marco D. Santambrogio – [email protected]. aggiornata al 21 Agosto 2014


Massimo Comune DivisoreMassimo Comune Divisore

• 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 Parte 0/4: La brutta notizia!notizia!

• Abbiamo un problema!!!! Dati due numeri interi, si trovi il MCD

3

how to solve it di Poyla G. - http://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.pdf


Come realizzare un algoritmoCome realizzare un algoritmo

• Parte 1/4: Capire il problema Quale e’ il problema generale che si

scerca di risolvere?

4


Parte 1/4: Capire il Parte 1/4: Capire il problemaproblema

• 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?Abbiamo solo P1 e P2?

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



•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 Parte 2/4: Fare/creare un pianopiano

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


P1P1: Fare/creare un piano: Fare/creare un piano

• 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.2P1.2: Fare/creare un piano: Fare/creare un piano

• 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 numeroB. Il numero è maggiore o uguale a 1

a. Se si FINEb. Se no, torna a A

10


P1.2P1.2: Chiariamo meglio…: Chiariamo meglio…

• 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 numeroB. Finché Il numero è minore di 1, torna ad

A

11


P1.1+P1.2P1.1+P1.2: : P1 P1 risoltorisolto

1. P1.1: Leggo un dato intero N12. P1.2: Finché N1 è minore di 1,

torna ad 13. P1.1: Leggo un dato intero N24. P1.2: Finché N2 è minore di 1,

torna ad 3

12


P2P2: Fare/creare un piano: Fare/creare un piano

• 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: 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: 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.3P2.3: Chiariamo meglio…: Chiariamo meglio…

• P2.3: Dobbiamo trovare il maggiore tra N numeri1. Il maggiore è il primo numero di N2. Vi è un altro numero in N?

A. Sia. Confronto il maggiore con il successivob. Il successivo è maggiore?c. Si: il maggiore diventa il successivod. Vado a 2

B. No: vado a 3

3. Il maggiore è maggiore

16



• P2.3: Dobbiamo trovare il maggiore tra N numeri1. Il maggiore è il primo numero di N2. Finché vi sono numeri in N?

a. Confronto il maggiore con il successivob. Il successivo è maggiore?c. Si: il maggiore diventa il successivod. Vado a 2


17


P2.1+P2.2P2.1+P2.2: Fare/creare un : Fare/creare un pianopiano

• 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

18

Come sono i numeri in {C}? (P2.2)

Sono divisori di un numero! (P1.1)


P2.1+P2.2P2.1+P2.2: Ricordiamo…: Ricordiamo…

• 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.2P2.1+P2.2: ma quindi…: ma quindi…

• 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

20

Se D1 è maggiore di N2?Se D2 è maggiore di N1?


P2.1+P2.2P2.1+P2.2: e ancora…: e ancora…

• 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

21

E cosa facciamo a P2.3?



• P2.3: Dobbiamo trovare il maggiore tra N numeri1. Il maggiore è il primo numero di N2. Finché vi sono numeri in N?

a. Confronto il maggiore con il successivob. Il successivo è maggiore?c. Si: il maggiore diventa il successivod. Vado a 2


22

E se gli N numeri fossero ordinatiin ordine crescente?


P2.3P2.3: Numeri ordinati: Numeri ordinati

• P2.3: Dobbiamo trovare il maggiore tra N numeri1. Il maggiore è l’ultimo numero di N

23

Essendo ordinati in ordine crescenteOgni successero è maggiore del precedente

Come usiamo questa idea?


P2.1+P2.2+P2.3P2.1+P2.2+P2.3

• 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

24

Come varia X?In ordine crescente :)


P2: P2: risoltorisolto

• 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


P1P1 ++ P2: P2: mettiamo tutto mettiamo tutto insiemeinsieme

1. P1.1: Leggo un dato intero N12. P1.2: Finché N1 è minore di 1, torna ad 13. P1.1: Leggo un dato intero N24. P1.2: Finché N2 è minore di 1, torna ad 35. X = 1 e TMP = 16. Finché X è minore o uguale a N1 e a N2

1. P2.1: X divide N1? e X divide N2?1. SI:

1. P2.2: X è divisore comune a N1 e a N22. P2.3: TMP = X

2. Incremento X

7. TMP è il MCD

26



• 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 Parte 3/4: Portare avanti il pianopiano

1. P1.1: Leggo un dato intero N12. P1.2: Finché N1 è minore di 1, torna ad 13. P1.1: Leggo un dato intero N24. P1.2: Finché N2 è minore di 1, torna ad 35. X = 1 e TMP = 16. Finché X è minore o uguale a N1 e a N2



2. Incremento X7. TMP è il MCD

28

Quante e quali variabili ci servono?



29

Quante e quali variabili ci servono?



1. P1.1: Leggo un dato intero N12. P1.2: Finché N1 è minore di 1,

torna ad 1

30



5. X = 1 e TMP = 1;

31


Definisco la condizioneDefinisco la condizione

32

A: X <= N1B: X <= N2

6. Finché X è minore o uguale a N1 e a N2

A B uscita0 0 00 1 01 0 01 1 1

6. Finché ((X<=N1) AND (X<=N2))



6. Finché X è minore o uguale a N1 e a N21. P2.1: X divide N1? e X divide N2?

1. SI: 1. P2.2: X è divisore comune a N1 e a N22. P2.3: TMP = X

2. Incremento X

33


Funzioni equivalenti 1Funzioni equivalenti 1

34

A: N1%XB: 0

A B uscita0 0 0!0 0 1

uscita è identica ad Auscita = A

NO!!!!!


Vediamo il codiceVediamo il codice

35


Vediamo il codice: debugVediamo il codice: debug

36


Vediamo il codice: debugVediamo il codice: debug

37


Funzioni equivalenti 1: Funzioni equivalenti 1: correttacorretta

38

A: N1%XB: 0

A B uscita0 0 1!0 0 0

uscita è identica all’inverso di Auscita = !A


Funzioni equivalenti 2Funzioni equivalenti 2

39

è equivalente a



1. P1.1: Leggo un dato intero N12. P1.2: Finché N1 è minore di 1, torna ad 13. P1.1: Leggo un dato intero N24. P1.2: Finché N2 è minore di 1, torna ad 35. X = 1 e TMP = 1;6. Finché X è minore o uguale a N1 e a N2



2. Incremento X

7. TMP è il MCD

40


MCD: Finito…MCD: Finito…

41



• 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…Ma scusate…

N1 = 200000N2 = 100000

43

Vogliamo veramente partire da 1Finché ((X<=N1) AND (X<=N2))

??????



• 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…Tornado nel passato…

45



• 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



47

A: N1%XB: N2%X

Finché X non divide N1 e N2

A B uscita0 0 10 1 01 0 01 1 0

Finché !(!(N1%x) AND !(N2%X))



48

A B !A !B (!A && !B) !(!A && !B)

0 0 1 1 1 00 1 1 0 0 1 1 0 0 1 0 11 0 0 1 0 1

Continuo finché 1


MCD: Finito!MCD: Finito!

49

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Come affrontare un problema… Marco D. Santambrogio –...

Documents

Transcript of DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Come affrontare un problema… Marco D. Santambrogio –...