Post on 01-May-2015
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmi e basi del CAlgoritmi e basi del C
Marco D. Santambrogio – marco.santambrogio@polimi.itVer. aggiornata al 8 Marzo 2013
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come non ricordare…Come non ricordare…
• … 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 pomodorohttp://rinabrundu.com/2012/03/07/ricorrenze-8-marzo-festa-del-
maccarone-al-pomodoro/
2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Bazinga!!!Bazinga!!!
3
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Info di servizioInfo di servizio
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
WAT?WAT?
• Spiegazioni: 7 su 61 chiedono di Spiegazioni: 7 su 61 chiedono di andare più pianoandare più piano
• Una persona ha trovato utili gli Una persona ha trovato utili gli esempi in C e 25 “esempi in C e 25 “entrambientrambi””
• In 19 su 61 avreste voluto vedere In 19 su 61 avreste voluto vedere più esempi in C!!più esempi in C!!
5
WAT
WATWAT
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ripasso di ieriRipasso di ieri
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
ObiettiviObiettivi
• 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
AlgoritmiAlgoritmi
8
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algortimo e ProgrammaAlgortimo e Programma
• Algoritmo DescrizioneDescrizione della soluzione di problemasoluzione di problema scritta in
modo da poter essere eseguita da un esecutoreesecutore (eventualmente diverso dall’autore dell’algoritmo)
Sequenza di istruzioniistruzioni che operano su datidati.
• Programma AlgoritmoAlgoritmo scritto in modo da poter essere eseguito
da un calcolatorecalcolatore (esecutore automatico)
99
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Acquisto DVDAcquisto DVD
10
Dove lo cerco?In quale settore?
Novita’Azione
…
Indicatori di settore
Novita ’
Trovato il settore, come trovo il mio DVD?
Ordine alfabetico
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Alogoritmo per lAlogoritmo per l’’acquisto DVDacquisto DVD
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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
CERCA: contesto e CERCA: contesto e problemaproblema• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Algoritmo CERCAAlgoritmo CERCA
• Noti s={d0, d1, …, dn}, ord. alfabeticamente DVD cercato = dt
1.Ci sono DVD? Allora
• Leggo il titolo del primo DVD in s• Se il titolo e’ il titolo cercato
Allora concludo la ricerca con successoAltrimenti passo al DVD successivo
Altrimenti concludo la ricerca con esito negativo
13
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
CERCA: osservazioniCERCA: osservazioni
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
CERCA… migliorataCERCA… migliorata
• Noti s={d0, d1, …, dn}, ord. alfabeticamente DVD cercato = dt
1.Ci sono DVD? Allora
• Leggo il titolo del DVD (dx) nel mezzo di s• Se il titolo di dx e’ il titolo cercato
1.Allora concludo la ricerca con successo2.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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Graficamente: NotiGraficamente: Noti
16
d0d0 d1d1 d2d2 d3d3 d4d4 d5d5 d6d6 d7d7 d8d8 d9d9 d10d10 d11d11
s={d0, d1, …, d11}
dt dt
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Leggo dLeggo dx x e lo confronto con de lo confronto con dtt
17
dx=d6
d6d6 dt dt <
d6d6 dt dt = ?
NO
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ricomincio Ricomincio sulla metasulla meta’’ superioresuperiore
18
dt dt
d6d6 d7d7 d8d8 d9d9 d10d10 d11d11
dx=d9
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Leggo dLeggo dx x e lo confronto con de lo confronto con dtt
19
dx=d9 d9d9 dt dt = ?
SI
Termino con successo la mia ricerca comprando d9
d9d9
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come si specifica un Come si specifica un algoritmo?algoritmo?
• Utilizzando dello pseudocodice
• Utilizzando dei diagrammi di flusso (aka schemi a blocchi)
20
Se A > B allora B = A altrimenti A = BSe A > B allora B = A altrimenti A = B
TestTestLeggi Scrivi
Inizio Fine Assegnamento
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Massimo Comune DivisoreMassimo Comune Divisore
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
MCD: pseudocodiceMCD: pseudocodice
1. Leggi A e B2. min= il minimo tra A e B3. tmp = 14. MCD = 15. Finche’ tmp < min
1. tmp = tmp + 12. Se tmp divide A e B
1. Allora MCD = tmp
6. Stampa MCD
22
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
MCD: diagramma di flussoMCD: diagramma di flusso
23
Inizio Leggi A e B
min=minimo{A,B}tmp=1MCD=1
tmp<min?tmp<min?
tmp = tmp + 1
tmp divide A e B
tmp divide A e B
MCD = tmp
Stampa MCD
Fine
no
no
si
si
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Benvenuti nel Benvenuti nel fantastico mondo fantastico mondo del Cdel C
24
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il primo programma: ciao Il primo programma: ciao mondomondo
25
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: stdio.hCiao Mondo: stdio.h
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: mainCiao Mondo: main
• Tutti i programmi in C contengono un elemento principale: Il main
• main contiene le istruzioni che verranno eseguite all’avvio del nostro programma
27
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: mainCiao Mondo: main
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: printfCiao Mondo: printf
29
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: printfCiao Mondo: printf
• Stampa a video il mesaggio “Ciao Mondo!”
• printf e’ contenuta in stdio.h
• Il messaggio da stampare e’ contenuto tra “”
30
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ciao Mondo: printfCiao Mondo: printf
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
32
Struttura di un Struttura di un programma Cprogramma C
inclusione librerie / per poter invocare funzioni utili (i/o, ...) /dichiarazione di variabili globali e funzioni
int main ( ) {
dichiarazione di variabili locali
istruzione 1; / tutti i tipi di operazioni, e cioè: /istruzione 2; / istr. di assegnamento / istruzione 3; / istr. di input / output /istruzione 4; / istr. di controllo (condizionali, cicli) /...istruzione N;
}
parte esecutiva
parte dichiarativa locale
parte dichiarativa globale
Ogni programma C deve contenere un modulo int main() {...}
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
33
• 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, ...)
Struttura di un Struttura di un programma Cprogramma C
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
34
Istruzioni semplici e Istruzioni semplici e compostecomposte
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Variabili e indirizziVariabili e indirizzi
• 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
int var;
0
1
2
3
var&var
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
36
Esecuzione degli Esecuzione degli assegnamentiassegnamenti
• 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 =
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come interagiamo con Come interagiamo con ““l’esternol’esterno”?”?
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Inserimento datiInserimento dati
• Problema Richiedi all’utente la sua altezza in
centrimentri e mostrala a video in metri
• Pseudocodice1.Scrivi “quanto sei alto?”2.Leggi altezzacm3.Altezzam = alteccacm/1004.Scrivi “sei alto: altezzam”
38
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Pausa… 15’Pausa… 15’
39
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Inserimento datiInserimento dati
• Problema Richiedi all’utente la sua altezza in
centrimentri e mostrala a video in metri
• Pseudocodice1.Scrivi “quanto sei alto?”2.Leggi altezzacm3.Altezzam = alteccacm/1004.Scrivi “sei alto: altezzam”
40
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Pseudocodice vs Codice CPseudocodice vs Codice C
• Pseudocodice
1. Scrivi “quanto sei alto?”2. Leggi altezzacm3. Altezzam = alteccacm/1004. Scrivi “sei alto: altezzam”
41
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un primo errore Un primo errore
42
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un secondo erroreUn secondo errore
43
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un terzo erroreUn terzo errore
44
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Soluzione correttaSoluzione corretta
45
L ’importanza dei tipi di dato
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Tipi di dato in CTipi di dato in C
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Mostra caratteriMostra caratteri
• Problema Si scriva un programma che richieda
l’inserimento di un carattere e lo mostri a video
47
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Tipo carattere e codifica ASCIITipo carattere e codifica ASCII
48
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ricordate il Ricordate il ““-32-32””
49
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un esempio di calcolo Un esempio di calcolo
50
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Problemi di fine giornata…Problemi di fine giornata…
• 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
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Fonti per lo studio + Fonti per lo studio + CreditsCredits• 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