algoritmi politecnico di milano progettare algoritmi politecnico di milano
TRANSCRIPT
![Page 1: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/1.jpg)
Algoritmi Politecnico di Milano
Progettare
Algoritmi Politecnico di Milano
![Page 2: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/2.jpg)
Fasi per progettare un algoritmo
• Formalizzare il problema
• Progettare
• Stendere l’algoritmo
• Verificare
![Page 3: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/3.jpg)
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
![Page 4: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/4.jpg)
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
![Page 5: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/5.jpg)
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
![Page 6: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/6.jpg)
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
![Page 7: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/7.jpg)
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
![Page 8: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/8.jpg)
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
![Page 9: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/9.jpg)
Progettare:3 Visualizzare la tassa
• Conosco l’istruzione di printf che mi permette di visualizzare una cella di memoria
tassa198
![Page 10: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/10.jpg)
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);}
![Page 11: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/11.jpg)
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
![Page 12: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/12.jpg)
Acquisisci i dati di ingresso
Calcola i risultati
Visualizza i risultati
Pattern 1
![Page 13: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/13.jpg)
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
![Page 14: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/14.jpg)
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
![Page 15: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/15.jpg)
• INPUT: carattere della tastiera
• OUTPUT:messaggi in alternativa– cifra– carattere
» EVENTUALMENTE vocale o consonante» EVENTUALMENTE minuscola
– Altro
Formalizzazione problema
![Page 16: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/16.jpg)
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
![Page 17: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/17.jpg)
/* 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
![Page 18: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/18.jpg)
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
![Page 19: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/19.jpg)
/* 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
![Page 20: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/20.jpg)
Istruzioni eseguite c video
?
scanf(c) 4 4
If ((c >= ‘0’) && (c<= ‘9’)) 4 4
printf(“cifra”); 4 4 cifra
Verificare
![Page 21: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/21.jpg)
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
![Page 22: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/22.jpg)
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
![Page 23: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/23.jpg)
Problema
• Data una sequenza di numeri naturali che finisce con 0 trovare il massimo dei numeri inseriti
![Page 24: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/24.jpg)
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
![Page 25: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/25.jpg)
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
![Page 26: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/26.jpg)
Progettare
Comincio a definire I passi fondamentali che deve fare l’algoritmo:
1.Acquisire I valori in input
2.Visualizzare il massimo
![Page 27: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/27.jpg)
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
![Page 28: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/28.jpg)
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
![Page 29: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/29.jpg)
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
![Page 30: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/30.jpg)
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
![Page 31: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/31.jpg)
Leggi il primo valoreInizializzaWhile (il valore non è l’ultimo) { Esegui l’operazione Leggi il prossimo valore }
Pattern 2
![Page 32: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/32.jpg)
Problema
• Visualizzare n naturali della tabellina del 2 con n scelto dall’utente
![Page 33: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/33.jpg)
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
![Page 34: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/34.jpg)
Raffinamento formalizzazione
Definizione:INPUT: n, quantità numeri da stampareOUTPUT: sequenza di n numeri multipli di 2
Raffinamento: Il Dialogo Uomo – Computer32 4 6
![Page 35: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/35.jpg)
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
![Page 36: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/36.jpg)
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
![Page 37: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/37.jpg)
Progettare
Pattern ciclo a conteggio
contatore = 0while (contatore < numero volte da ripetere){
azione da ripeterecontatore = contatore + 1;
}
![Page 38: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/38.jpg)
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
![Page 39: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/39.jpg)
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
![Page 40: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/40.jpg)
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;}
![Page 41: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/41.jpg)
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
![Page 42: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/42.jpg)
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
![Page 43: Algoritmi Politecnico di Milano Progettare Algoritmi Politecnico di Milano](https://reader035.vdocumenti.com/reader035/viewer/2022081505/5542eb4f497959361e8bf055/html5/thumbnails/43.jpg)
• 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