DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmi e basi del C
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 8 Marzo 2013
Come non ricordare…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• … che giornata sia oggi
 8 marzo 1459: nasce Bernardino Corio
• Storico italiano
 8 marzo 1728: muore Giovanni Mario
Crescimbeni
• Poeta e critico letterario italiano
 8 marzo 1882: Arturo Graf scrive una lettera a
Mario Rapisardi
• Entrambi scrittori e poeti italiani
• Ma è anche:
 La festa del maccarone al pomodoro
http://rinabrundu.com/2012/03/07/ricorrenze-8-marzo-festa-del-maccarone-alpomodoro/
2
Bazinga!!!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
Info di servizio
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Laboratori: divisione in gruppi
 Non stiamo andando benissimo
 9 gruppi il lunedi’
 3 gruppo il giovedi’
• Feedback sulle lezioni
 Se date una valutazione ≤ 3 sul quanto la spiegazione sia
risultata chiara, vi chiederei cortesemente di spiegare nelle
note a cosa e’ dovuto questo dato
• La “Survey” e’ sempre aperta, se volete potete continuare
a inserire i vostri dati
• No, il “gufo” non diventa milanista…
 e’ milanista!!
4
WAT?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Spiegazioni: 7 su 61 chiedono di andare
più piano
WAT
• Una persona ha trovato utili gli esempi
in C e 25 “entrambi”
• In 19 su 61 avreste voluto vedere più
esempi in C!!
5
Ripasso di ieri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Concetto ambiguo di informazione
 Informazione = dati + istruzioni
 Informazione = dati con significato
• Esempio: il numero 3 è un semplice dato,
diventa entità di informazione quando lo si
contestualizza
•
•
•
•
Programmabilità del calcolatore
Macchina di von Neumann
Comunicazione non ambigua
Calcolo come calcolo di funzioni
6
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Algoritmi
 Pseudocodice
 Diagramma di flusso
• Una prima introduzione al C
 Un primo programma
 Tipi di dato
 Strutture di controllo
7
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmi
8
Algortimo e Programma
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Algoritmo
 Descrizione della soluzione di problema scritta in modo da
poter essere eseguita da un esecutore (eventualmente
diverso dall’autore dell’algoritmo)
 Sequenza di istruzioni che operano su dati.
• Programma
 Algoritmo scritto in modo da poter essere eseguito da un
calcolatore (esecutore automatico)
9
Acquisto DVD
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Novita’
Novita’
Dove lo cerco?
In quale settore?
Indicatori di settore
Azione
…
Trovato il settore, come
trovo il mio DVD?
Ordine alfabetico
10
Alogoritmo per l’acquisto DVD
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1. Acquisisci il nome del settore (s) del
DVD (d)
2. Vai al settore (s)
3. Cerca (t)
4. Prendi il DVD (d)
• Acquisisci e Cerca sono anche loro
algoritmi
11
CERCA: contesto e problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Contesto
 Sei nel settore (s) corretto
 Nel settore sono presenti diversi DVD
• Il settore puo’ essere visto come un insieme di
DVD: s={d0, d1, …, dn}
• Problema
 Devo trovare il DVD (dt) tra tutti i DVD presenti
nel settore (s)
 Aiuto: il settore e’ ordinato
• I DVD sono ordinati alfabeticamente
12
Algoritmo CERCA
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Noti
 s={d0, d1, …, dn}, ord. alfabeticamente
 DVD cercato = dt
1.Ci sono DVD?
 Allora
1.
2.
Leggo il titolo del primo DVD in s
Se il titolo e’ il titolo cercato
Allora concludo la ricerca con successo
Altrimenti passo al DVD successivo
 Altrimenti concludo la ricerca con esito
negativo
13
CERCA: osservazioni
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Cosa succede se il settore e’ vuoto?
• Come funziona la mia ricerca?
 Se in s vi sono 10000 DVD e io cerco
Zorro?
 Scenario ancora peggiore
• Voglio cercare il numero del mio professore di
IEIM (Santambrogio) nella rubrica telefonica di
Milano..
• Esistono diversi modi per risolvere un
problema
14
CERCA… migliorata
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Noti
 s={d0, d1, …, dn}, ord. alfabeticamente
 DVD cercato = dt
1. Ci sono DVD?
 Allora
1.
2.
Leggo il titolo del DVD (dx) nel mezzo di s
Se il titolo di dx e’ il titolo cercato
– Allora concludo la ricerca con successo
– Altrimenti se dx < dt
» allora ricomincio da 1 considerando la meta’ superiore di s
» Altrimenti ricomincio da 1 considerando la meta’ inferiore di
s
 Altrimenti concludo la ricerca con esito negativo
15
Graficamente: Noti
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
s={d0, d1, …, d11}
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
16
Leggo dx e lo confronto con dt
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
dx=d6
d6
=
dt
?
NO
d6
<
dt
17
Ricomincio sulla meta’ superiore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
d6
d7
d8
d9
d10
d11
dx=d9
18
Leggo dx e lo confronto con dt
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
dx=d9
d9
=
dt
?
SI
Termino con successo la
mia ricerca comprando d9
19
Come si specifica un algoritmo?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Utilizzando dello pseudocodice
Se A > B allora B = A altrimenti A = B
• Utilizzando dei diagrammi di flusso (aka
schemi a blocchi)
Inizio
Leggi
Fine
Test
Assegnamento
Scrivi
20
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
• Esempi
 Dati A=12, B=15
• Divisori comuni: 1, 3 - MCD=3
 Dati A=10, B=30 e C=20
• Divisori comuni: 1, 2, 5, 10 - MCD=10
21
MCD: pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1.
2.
3.
4.
5.
Leggi A e B
min= il minimo tra A e B
tmp = 1
MCD = 1
Finche’ tmp < min
1. tmp = tmp + 1
2. Se tmp divide A e B
1. Allora MCD = tmp
6. Stampa MCD
22
MCD: diagramma di flusso
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Inizio
Leggi A e B
min=minimo{A,B}
tmp=1
MCD=1
Stampa MCD
no
tmp<min?
si
tmp = tmp + 1
Fine
tmp divide A e B
no
si
MCD = tmp
23
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Benvenuti nel
fantastico mondo del
C
24
Il primo programma: ciao mondo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
25
Ciao Mondo: stdio.h
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Come prima cosa,
dobbiamo includere le
librerie necessarie al
funzionamento del
nostro programma.
• La libreria stdio.h
 Standard Input Output
 Permette di utilizzare I
comandi necessari per
richiedere dati o
visualizzare dei
messaggi.
26
Ciao Mondo: main
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Tutti i programmi in C
contengono un
elemento principale:
 Il main
• main contiene le
istruzioni che verranno
eseguite all’avvio del
nostro programma
27
Ciao Mondo: main
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• La sequenza di istruzioni
che caratterizzano il main
sono racchiuse tra
parentesi graffe
• Tale blocco di istruzioni e’
anche noto come corpo
• Ogni istruzione deve
essere seguita da un punto
e virgola
28
Ciao Mondo: printf
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
29
Ciao Mondo: printf
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Stampa a video il
mesaggio “Ciao
Mondo!”
• printf e’ contenuta in
stdio.h
• Il messaggio da
stampare e’ contenuto
tra “”
30
Ciao Mondo: printf
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• return e' un comando che ci
permette di comunicare con il
sistema ospite
• In questo caso viene
utilizzato per comunicare lo
stato di terminazione del
programma
• 0 indica una terminazione
corretta del nostro
programma
31
Struttura di un programma C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
parte dichiarativa globale
inclusione librerie / per poter invocare funzioni utili (i/o, ...) /
dichiarazione di variabili globali e funzioni
int main ( ) {
parte dichiarativa locale
dichiarazione di variabili locali
istruzione 1;
istruzione 2;
istruzione 3;
istruzione 4;
...
istruzione N;
/ tutti i tipi di operazioni, e cioè: /
/ istr. di assegnamento /
/ istr. di input / output /
/ istr. di controllo (condizionali, cicli) /
parte esecutiva
}
Ogni programma C deve contenere un modulo int main() {...}
32
Struttura di un programma C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte dichiarativa: contiene le dichiarazioni degli
elementi del programma
 Dati, ed eventualmente funzioni (ma solo nella parte globale)
• Parte esecutiva: contiene le istruzioni da eseguire,
che ricadono nelle categorie:
 Istruzioni di assegnamento ()
 Strutture di controllo:
• Condizionali (if-then-else e switch)
• Iterative, o cicli (while, do e for)
 Istruzioni di Input/Output (printf, scanf, ...)
33
Istruzioni semplici e composte
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Sequenze di istruzioni semplici
 Ogni istruzione semplice termina con ;
 ; è detto il “terminatore” dell’istruzione
• Si possono raggruppare più istruzioni in
sequenza tra { e } a costituire un blocco
 Il blocco costituisce una “super-istruzione”
• Non è necessario il ; dopo }, in quanto il
blocco è già una istruzione
 e non necessita del terminatore per diventarla
34
Variabili e indirizzi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
int var;
&var
2
var
1
0
• Supponiamo che la dichiarazione riservi la zona di
memoria all’indirizzo 1
• var indica il contenuto della cella di memoria
• &var indica l’indirizzo della cella di memoria
35
Esecuzione degli assegnamenti
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•
valutazione dell’espressione che
compare a destra del simbolo =

•
il valore delle variabili che vi compaiono
si trova memorizzato nelle celle
corrispondenti, e da lì è letto
memorizzazione del risultato
dell'espressione nella variabile a
sinistra del simbolo =
36
Come interagiamo con “l’esterno”?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Input - Output
 printf viene utiizzata per fornire un output
del programma a video
 scanf viene utilizzato per fornire degli input,
e.g. da tastiera, al nostro programma
37
Inserimento dati
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Richiedi all’utente la sua altezza in
centrimentri e mostrala a video in metri
• Pseudocodice
1.Scrivi “quanto sei alto?”
2.Leggi altezzacm
3.Altezzam = alteccacm/100
4.Scrivi “sei alto: altezzam”
38
Pausa… 15’
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
39
Inserimento dati
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Richiedi all’utente la sua altezza in
centrimentri e mostrala a video in metri
• Pseudocodice
1.Scrivi “quanto sei alto?”
2.Leggi altezzacm
3.Altezzam = alteccacm/100
4.Scrivi “sei alto: altezzam”
40
Pseudocodice vs Codice C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Pseudocodice
1.
2.
3.
4.
Scrivi “quanto sei alto?”
Leggi altezzacm
Altezzam = alteccacm/100
Scrivi “sei alto: altezzam”
41
Un primo errore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
42
Un secondo errore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
43
Un terzo errore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
44
Soluzione corretta
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
45
Tipi di dato in C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• In C esistono diversi tipi di dato built-in, tra cui




int: numeri interi
float: numeri con virgola (singola precisione)
double: numeri con virgola (doppia precisione)
char: caratteri (sono interi che possono variare tra
0-255)
• Inoltre il C fornisce anche la possibilità di
definire dei nuovi tipi di dato
46
Mostra caratteri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Si scriva un programma che richieda
l’inserimento di un carattere e lo mostri a
video
47
Tipo carattere e codifica ASCII
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
48
Ricordate il “-32”
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
49
Un esempio di calcolo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
50
Problemi di fine giornata…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Scrivere un programma che, letti due
numeri, individua quello maggiore
• Rappresentare in pseudocodice
l’agoritmo che, letti 3 numeri, ne calcola
il minimo comune multiplo
51
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 Informatica arte e mestiere, S. Ceri, D.
Mandrioli, L. Sbattella, McGrawHill
• Capitolo 3
 Introduzione ai sistemi informatici, D. Sciuto,
G. Buonanno, L. Mari, 4a Ed, McGrawHill
• Capitolo 3, 4
 The Art & Craft of Computing, S. Ceri, D.
Mandrioli, L. Sbattella, Addison-Wesley
• Capitolo 3
• Credits