DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmi e basi del C
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 4 Ottobre 2013
What it’s all about!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
2
What it’s all about!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
What it’s all about!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
4
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
5
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmi
6
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)
7
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 0/4: La brutta notizia!
how to solve it di Poyla G. - http://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.pdf
8
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 1/4: Capire il problema
 Quale e’ il problema generale che si scerca
di risolvere?
9
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
•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
10
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
11
Come realizzare un algoritmo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Parte 4/4: Ragionare e comprendere
 Comprendere quello che si è fatto e dove
l’algoritmo individuato possa essere
applicato al meglio
La pratica è fondamentale!
12
Testare il proprio lavoro!!!
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Se vi è qualche cosa che non funziona
nel vostro programma/algoritmo, gli
utenti lo troveranno!
13
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
14
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
15
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
16
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
17
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
18
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
19
Graficamente: Noti
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
s={d0, d1, …, d11}
d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
20
Leggo dx e lo confronto con dt
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
dx=d6
d6
=
dt
?
NO
d6
<
dt
21
Ricomincio sulla meta’ superiore
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
d6
d7
d8
d9
d10
d11
dx=d9
22
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
23
Pausa… 5’
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
24
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
25
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
26
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
27
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
28
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Benvenuti nel
fantastico mondo del
C
29
Il primo programma: ciao mondo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
30
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.
31
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
32
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
33
Ciao Mondo: printf
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
34
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 “”
35
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
36
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
37
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 how to solve it, Poyla G
• http://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.p
df
 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