Algoritmi Politecnico di Milano

Progettare

Algoritmi Politecnico di Milano

Fasi per progettare un algoritmo

• Formalizzare il problema

• Progettare

• Stendere l’algoritmo

• Verificare

problema

• Problema: Un comune decide di mettere una tassa sul passo carrabile di 9.8 euro al metro quadro. Ogni passo carrabile è stato denunciato definendone le dimensioni in altezza e larghezza.

Calcolare la tassa che si deve pagare per ogni passo carrabile

Formalizzazione problema

• Problema: Un comune decide di mettere una tassa sul passo carrabile di 9.8 euro al metro quadro. Ogni passo carrabile è stato denunciato definendone le dimensioni in altezza e larghezza.

Calcolare la tassa che si deve pagare per ogni passo carrabile

INPUT: altezza e larghezza passo carrabileOUTPUT: tassa

Raffinamento formalizzazione

Definizione:INPUT: altezza e larghezza passo carrabileOUTPUT: tassa

Raffinamento: Il Dialogo Uomo – Computer Inserisci la lunghezza del passo carrabile: 4 Inserisci la larghezza del passo carrabile: 5 tassa da pagare 196

Progettare

Comincio a definire I passi fondamentali che deve fare l’algoritmo:

1.Acquisire I valori in input

2.Calcolare la tassa

3.Visualizzare la tassa

Progettare: 1 acquisire I valori in input

• Ogni valore digitato dall’utente (es. 4 e 5) deve essere memorizzato per poter essere utilizzato nel calcolo dell’area – Decido di utilizzare due celle di memoria:

– Conosco che l’operazione che prende I dati da tastiera e li deposita in memoria è per la macchina C la scanf

scanf(lunghezza)

scanf(larghezza)

lunghezza larghezza

Progettare: 2 Calcolare la tassa

• So calcolare la tassa “a mano”tassa = lunghezza * larghezza * 9.8

• Dalla formula deduco che mi serve utilizzare un’altra cella di memoria per memorizzare il valore della tassa

• Conosco l’istruzione di assegnamento della macchina C che ha lo stesso aspetto della formula matematica

tassa

Progettare:3 Visualizzare la tassa

• Conosco l’istruzione di printf che mi permette di visualizzare una cella di memoria

tassa198

Stendere l’algoritmomain(){

/* Acquisire I valori in input */ printf("Inserisci la lunghezza del passo carrabile:" ); scanf (lunghezza); printf("Inserisci la larghezza del passo carrabile:" ); scanf(larghezza); /* Calcolare la tassa */ tassa = lunghezza * larghezza * 9.8; /* Visualizzare la tassa */ printf(“tassa da pagare “); printf(tassa);}

Verificare: simuliamo l’esecuzione

main(){ /* Acquisire I valori in input */ printf("Inserisci la lunghezza del passo carrabile:" ); scanf (lunghezza); printf("Inserisci la larghezza del passo carrabile:" ); scanf(larghezza); /* Calcolare la tassa */ tassa = lunghezza * larghezza * 9.8; /* Visualizzare la tassa */ printf(“tassa da pagare “); printf(tassa);}

tassa?

lunghezza?

larghezza?

tassa?

lunghezza4

larghezza5

tassa198

lunghezza4

larghezza5

Acquisisci i dati di ingresso

Calcola i risultati

Visualizza i risultati

Pattern 1

Esercizi simili• Calcolare il volume di un cilindro conoscendo raggio e altezza

• Vengono forniti da tastiera i risultati di un referendum:– Numero iscritti a votare– Numero votanti– Numero si– Numero no

Calcolare la percentuale di votanti sul totale degli iscritti, le percentuali dei si e dei no rispetto al numero dei votanti

Problema

• Scrivere un programma che legge in ingresso un carattere e stampa se corrisponde a una cifra o a una lettera alfabetica o a un altro carattere, nel caso sia una lettera segnalare il caso particolare che sia una vocale o una consonante e il caso particolare che sia minuscola. Es:

• 3 cifra• D lettera consonante• e lettera vocale minuscola • d lettera consonante minuscola• E lettera vocale • < altro carattere

• INPUT: carattere della tastiera

• OUTPUT:messaggi in alternativa– cifra– carattere

» EVENTUALMENTE vocale o consonante» EVENTUALMENTE minuscola

– Altro

Formalizzazione problema

Acquisisco il carattere

Emetto i messaggi in alternativa

Progettare

/* acquisisco il carattere /*

scanf(c);

/* Emetto i messaggi in alternativa */

If (c è una cifra)

printf(“cifra”);

else if (c è una lettera)

analizzo la lettera

else

printf(“altro carattere”);

Le azioni printf sono in alternativa uso if

I casi sono mutuamente esclusivi

L’azione viene eseguita dalla macchina C solo nel

caso c sia una lettera

/* analizzo la lettera */

If (c è una vocale)

printf(“vocale”);

else

printf(“consonante”);

If (c è minuscola)

printf(“minuscola”);

Progettare

I casi non sono mutuamente esclusivi: c

può essere una vocale ed essere minuscola

c è una cifra (c >= ‘0’) && (c<= ‘9’)

c è una lettera(c >= ‘a’) && (c <= ‘z’) ||(c >= ‘A’) && (c <= ‘Z’)

c è una vocale(c == ‘a’) || (c == ‘e’) || (c== ‘i’) || (c == ‘o’) || (c == ‘u’)

c è minuscola (c >= ‘a’) && (c <= ‘z’)

Progettare

So che nella tabella ascii le lettere sono codificate

sequenzialmente seguendo l’ordine

/* acquisisco il carattere /*

scanf(c);

/* Emetto i messaggi in alternativa */

If ((c >= ‘0’) && (c<= ‘9’))

printf(“cifra”);else if ((c >= ‘a’) && (c <= ‘z’) || (c >= ‘A’) && (c <= ‘Z’) ) /* analizzo la lettera */ If ((c == ‘a’) || (c == ‘e’) || (c== ‘i’) || (c == ‘o’) || (c == ‘u’)) printf(“vocale”); else printf(“consonante”); If ((c >= ‘a’) && (c <= ‘z’)) printf(“minuscola”);else printf(“altro carattere”);

Stendere l’algoritmo

Istruzioni eseguite c video

?

scanf(c) 4 4

If ((c >= ‘0’) && (c<= ‘9’)) 4 4

printf(“cifra”); 4 4 cifra

Verificare

Istruzioni eseguite c video

?

scanf(c) d d

If ((c >= ‘0’) && (c<= ‘9’)) d d

else if ((c >= ‘a’) && (c <= ‘z’) || d d (c >= ‘A’) && (c <= ‘Z’) )

If ((c == ‘a’) || (c == ‘e’) || (c== ‘i’) d d || (c == ‘o’) || (c == ‘u’))

printf(“consonante”); d d consonante

If ((c >= ‘a’) && (c <= ‘z’)) d d consonante

printf(“minuscola”); d d consonante minuscola

Verificare

Esercizi simili

• Date le misure a e b di un rettangolo potenziale

(a e b possono essere nulle o negative) si vuole sapere si tratta di un quadrato, di un rettangolo, di un segmento, di un punto o di un caso impossibile

• Dati tre numeri interi calcolare il massimo e stamparlo

Problema

• Data una sequenza di numeri naturali che finisce con 0 trovare il massimo dei numeri inseriti

Formalizzazione problema

• Problema: Data una sequenza di numeri naturali che finisce con 0 trovare il massimo dei numeri inseriti

INPUT: sequenza di naturali che finisce con 0

OUTPUT: numero massimo

Raffinamento formalizzazione

Definizione:INPUT: sequenza di naturali che finisce con 0

OUTPUT:numero massimo

Raffinamento: Il Dialogo Uomo – Computer 34 61 9 0 massimo 61

Progettare

Comincio a definire I passi fondamentali che deve fare l’algoritmo:

1.Acquisire I valori in input

2.Visualizzare il massimo

Progettare

Acquisire I valori in input• Provo a risolvere io il problema e osservo le operazioni

che compio

• Noto che pur non memorizzando tutti I numeri riesco a trovare il massimo

• Noto che in ogni momento memorizzo il numero appena inserito dall’utente e il massimo dei numeri precedentemente inseriti

• In memoria definisco le variabili:

massimo56

numero 8

Progettare

Acquisire I valori in input• Provo a risolvere io il problema e osservo le operazioni

che compio

• Noto che continuo a ripetere il confronto fra il numero inserito e il massimo dei precedenti

• Noto che se il numero inserito è più grande diventa il massimo che memorizzo

main() {

/* Acquisire I valori in input */

scanf(numero);

massimo = numero;

while (numero != 0)

{ if (numero >massimo)

massimo = numero;

scanf(numero);

}

/* Visualizzare il massimo */

printf(massimo);

}

Stendere l’algoritmo

Il massimo è il primo numero

Non è l’ultimo numero

Noto che continuo a ripetere il confronto fra il numero inserito e

il massimo dei precedenti

Noto che se il numero inserito è più grande diventa il

massimo che memorizzo

Istruzioni eseguite c massimo video

? ?

scanf(numero) 34 ? 34

massimo = numero; 34 34 34while (numero != 0) 34 34 34if (numero >massimo) 34 34 34

scanf(numero); 61 34 34 61

While (numero != 0) 61 34 34 61

if (numero >massimo) 61 34 34 61

massimo = numero; 61 61 34 61

scanf(numero); 9 61 34 61 9

While (numero != 0) 9 61 34 61 9

if (numero >massimo) 9 61 34 61 9

scanf(numero); 0 61 34 61 9

While (numero != 0) 0 61 34 61 9 0

printf(massimo) 0 61 61

Verificare

Leggi il primo valoreInizializzaWhile (il valore non è l’ultimo) { Esegui l’operazione Leggi il prossimo valore }

Pattern 2

Problema

• Visualizzare n naturali della tabellina del 2 con n scelto dall’utente

Formalizzazione problema

• Problema: Visualizzare n naturali della tabellina del 2 con n scelto dall’utente

INPUT: n, quantità numeri da stampare

OUTPUT: sequenza di n numeri multipli di 2

Raffinamento formalizzazione

Definizione:INPUT: n, quantità numeri da stampareOUTPUT: sequenza di n numeri multipli di 2

Raffinamento: Il Dialogo Uomo – Computer32 4 6

Progettare

Comincio a definire I passi fondamentali che deve fare l’algoritmo:

1.Acquisire il valore n

2.Visualizzo i primi n multipli di 2

Progettare

Visualizzo i primi n multipli di 2• Parto dal risultato:

• Devo visulizzare n numeri

ciclo che si ripete n volte e che contiene una printf del numero da visualizzare

• Uso il pattern del ciclo a conteggio

Progettare

Pattern ciclo a conteggio

contatore = 0while (contatore < numero volte da ripetere){

azione da ripeterecontatore = contatore + 1;

}

main()

{

/* acquisisco quantità n */

scanf(n);

/* visualizzo i primi n multipli di n */

Contatore = 0;

While (contatore < n)

{

printf (multiplo2);

contatore = contatore + 1;

}

Stendere l’algoritmo

Mi accorgo che qualcosa non funziona, la variabile

multiplo2 è solo visualizzata e mai valorizzata:

Provo a fare il trace

Istruzioni eseguite n contatore multiplo2 video

? ? ?

scanf(n) 3 ? ? 3

contatore = 0 3 0 ? 3

while (contatore < n) 3 0 ? 3printf(multiplo2) 3 0 ? ?

Mi fermo qui: sul video appare un numero qualsiasi mentre dovrebbe essere 2 e poi 4 e poi 6 …questi sono i valori che dovrebbe assumere multiplo2 …

Verificare

Stendere l’algoritmo

main(){/* acquisisco quantità n */scanf(n);/*visualizzo i primi n multipli di n */multiplo2 = 2;contatore = 0;while (contatore < n){ printf (multiplo2); multiplo2 = multiplo2 + 2; contatore = contatore + 1;}

main(){/* acquisisco quantità n */scanf(n);/*visualizzo i primi n multipli di n */multiplo2 = 0;contatore = 0;while (contatore < n){ multiplo2 = multiplo2 + 2; printf (multiplo2); contatore = contatore + 1;}

main()

{

/* acquisisco quantità n */

scanf(n);

/* visualizzo i primi n multipli di n */

contatore = 1;

While (contatore <= n)

{

printf (contatore*2);

contatore = contatore + 1;

}

Stendere l’algoritmo

Noto che il numero da stampare è sempre il doppio

di contatore: aggiusto l’algoritmo di conseguenza

Problemi simili

• Visualizzare a video la parola ciao un numero di volte scelto dall’utente

• Calcolare il prodotto di una sequenza di numeri che termina con 0

• Stampare il valore della potenza di base m ed esponente n > 0

• data una sequenza di n punti nel piano con n scelto dall’utente, stampare la distanza massima dall’origine degli assi dei punti introdotti

• Modificare il programma precedente stampando le coordinate del punto di distanza massima

• Modificare il programma precedente stampando la distanza media

• Scompongo la soluzione in un piccolo numero di “big step”• Comicio a riempire l’algoritmo con printf e scanf facendomi guidare

dal dialogo uomo computer• Parto dal risultato da ottenere e torno indietro• Uso l’analogia: come potrei farlo io a mano?• Uso pattern conosciuti• Verifico, verifico, verifico …

suggerimenti