Algoritmi
Algoritmi
Politecnico di Milano
Politecnico di Milano
Progettare
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 carrabile
OUTPUT: tassa
Raffinamento formalizzazione
Definizione:
INPUT: altezza e larghezza passo carrabile
OUTPUT: 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:
lunghezza
larghezza
– 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)
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
tassa
• Conosco l’istruzione di assegnamento della
macchina C che ha lo stesso aspetto della
formula matematica
Progettare:3 Visualizzare la tassa
198
tassa
• Conosco l’istruzione di printf che mi permette di
visualizzare una cella di memoria
Stendere l’algoritmo
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);
}
Verificare: simuliamo l’esecuzione
?
?
main()
tassa
lunghezza
{
/* Acquisire I valori in input */
printf("Inserisci la lunghezza del passo carrabile:" );
scanf (lunghezza);
printf("Inserisci la larghezza del passo carrabile:" );
scanf(larghezza);
?
4
/* Calcolare la tassa */
tassa
lunghezza
tassa = lunghezza * larghezza * 9.8;
/* Visualizzare la tassa */
198
4
printf(“tassa da pagare “);
tassa
lunghezza
printf(tassa);
}
?
larghezza
5
larghezza
5
larghezza
Pattern 1
Acquisisci i dati di ingresso
Calcola i risultati
Visualizza i risultati
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
Formalizzazione problema
• INPUT: carattere della tastiera
• OUTPUT:messaggi in alternativa
– cifra
– carattere
» EVENTUALMENTE
» EVENTUALMENTE
– Altro
vocale o consonante
minuscola
Progettare
Acquisisco il carattere
Emetto i messaggi in alternativa
/* acquisisco il carattere /*
scanf(c);
/* Emetto i messaggi in alternativa */
If (c è una cifra)
Le azioni printf sono in
alternativa uso if
I casi sono mutuamente
esclusivi
printf(“cifra”);
else if (c è una lettera)
analizzo la lettera
else
printf(“altro carattere”);
L’azione viene eseguita
dalla macchina C solo nel
caso c sia una lettera
Progettare
/* analizzo la lettera */
If (c è una vocale)
printf(“vocale”);
else
printf(“consonante”);
If (c è minuscola)
printf(“minuscola”);
I casi non sono
mutuamente esclusivi: c
può essere una vocale ed
essere minuscola
Progettare
c è una cifra
(c >= ‘0’) && (c<= ‘9’)
c è una lettera
(c >= ‘a’) && (c <= ‘z’) ||
(c >= ‘A’) && (c <= ‘Z’)
So che nella tabella ascii
le lettere sono codificate
sequenzialmente
seguendo l’ordine
c è una vocale
(c == ‘a’) || (c == ‘e’) || (c== ‘i’) || (c == ‘o’) || (c == ‘u’)
c è minuscola
(c >= ‘a’) && (c <= ‘z’)
Stendere l’algoritmo
/* 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”);
Verificare
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’) ||
(c >= ‘A’) && (c <= ‘Z’) )
d
d
If ((c == ‘a’) || (c == ‘e’) || (c== ‘i’)
|| (c == ‘o’) || (c == ‘u’))
d
d
printf(“consonante”);
d
d consonante
If ((c >= ‘a’) && (c <= ‘z’))
d
d consonante
printf(“minuscola”);
d
d consonante minuscola
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:
8
numero
56
massimo
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
•
Stendere l’algoritmo
main() {
Il massimo è
/* Acquisire I valori in inputil*/primo
scanf(numero);
numero
Non è
l’ultimo
numero
massimo = numero;
while (numero != 0)
{ if (numero >massimo)
massimo = numero;
Noto che continuo a ripetere il
confronto fra il numero inserito e
il massimo dei precedenti
scanf(numero);
}
/* Visualizzare il massimo */
printf(massimo);
}
Noto che se il numero inserito
è più grande diventa il
massimo che memorizzo
Verificare
Istruzioni eseguite
c
massimo
video
?
?
scanf(numero)
34
?
34
massimo = numero;
while (numero != 0)
if (numero >massimo)
34
34
34
34
34
34
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
Pattern 2
Leggi il primo valore
Inizializza
While (il valore non è l’ultimo)
{
Esegui l’operazione
Leggi il prossimo valore
}
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 stampare
OUTPUT: sequenza di n numeri multipli di 2
Raffinamento: Il Dialogo Uomo – Computer
3
246
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 = 0
while (contatore < numero volte da ripetere)
{
azione da ripetere
contatore = contatore + 1;
}
Stendere l’algoritmo
main()
{
/* acquisisco quantità n */
scanf(n);
/* visualizzo i primi n multipli di n */
Contatore = 0;
While (contatore < n)
{
printf (multiplo2);
contatore = contatore + 1;
}
Mi accorgo che qualcosa
non funziona, la variabile
multiplo2 è solo visualizzata
e mai valorizzata:
Provo a fare il trace
Verificare
Istruzioni eseguite
n
contatore
multiplo2
video
?
?
?
scanf(n)
3
?
?
3
contatore = 0
3
0
?
3
while (contatore < n)
printf(multiplo2)
3
3
0
0
?
?
3
?
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 …
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;
}
Stendere l’algoritmo
main()
{
/* acquisisco quantità n */
scanf(n);
/* visualizzo i primi n multipli di n */
contatore = 1;
While (contatore <= n)
{
printf (contatore*2);
contatore = contatore + 1;
}
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
suggerimenti
• 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 …