DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Algoritmi e basi del C Marco D. Santambrogio –...

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Algoritmi e basi del CAlgoritmi e basi del C

Marco D. Santambrogio – [email protected]. aggiornata al 9 Agosto 2013


ObiettiviObiettivi

• Algoritmi Pseudocodice Diagramma di flusso

• Una prima introduzione al C Un primo programma Tipi di dato Strutture di controllo

2


AlgoritmiAlgoritmi

3


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)

44


Acquisto DVDAcquisto DVD

5

Dove lo cerco?In quale settore?

Novita’Azione

…

Indicatori di settore

Novita ’

Trovato il settore, come trovo il mio DVD?

Ordine alfabetico


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

6


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

7


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

8


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

9


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

10


Graficamente: NotiGraficamente: Noti

11

d0d0 d1d1 d2d2 d3d3 d4d4 d5d5 d6d6 d7d7 d8d8 d9d9 d10d10 d11d11

s={d0, d1, …, d11}

dt dt


Leggo dLeggo dx x e lo confronto con de lo confronto con dtt

12

dx=d6

d6d6 dt dt <

d6d6 dt dt = ?

NO


Ricomincio Ricomincio sulla metasulla meta’’ superioresuperiore

13

dt dt

d6d6 d7d7 d8d8 d9d9 d10d10 d11d11

dx=d9


Leggo dLeggo dx x e lo confronto con de lo confronto con dtt

14

dx=d9 d9d9 dt dt = ?

SI

Termino con successo la mia ricerca comprando d9

d9d9


Come si specifica un Come si specifica un algoritmo?algoritmo?

• Utilizzando dello pseudocodice

• Utilizzando dei diagrammi di flusso (aka schemi a blocchi)

15

Se A > B allora B = A altrimenti A = BSe A > B allora B = A altrimenti A = B

TestTestLeggi Scrivi

Inizio Fine Assegnamento


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

16


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

17


MCD: diagramma di flussoMCD: diagramma di flusso

18

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


Pausa… 15’Pausa… 15’

19


Benvenuti nel Benvenuti nel fantastico mondo fantastico mondo del Cdel C

20


Il primo programma: ciao Il primo programma: ciao mondomondo

21


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.

22


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

23


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

24


Ciao Mondo: printfCiao Mondo: printf

25



• Stampa a video il mesaggio “Ciao Mondo!”

• printf e’ contenuta in stdio.h

• Il messaggio da stampare e’ contenuto tra “”

26



• 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

27


28

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() {...}


29

• 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


30

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


31

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 =


32

x = 23;w = 'a';y = z;alfa = x + y;r3 = ( alfa * 43 – xgg ) * ( delta – 32 * j );x = x + 1;

Abbreviazioni (operatori di assegnamento):

a = a + 7; a = a * 5; a = a + 1; a = a - 1;a += 7; a *= 5; ++a; --a;

Esempi di assegnamentoEsempi di assegnamento

Istruzioni della forma variabile = variabile operatore espressione;si possono scrivere come: variabile operatore = espressione;


33

• Operatori aritmetici in C: * per la moltiplicazione e / per la divisione La divisione tra interi elimina il resto (quoziente):

13 / 5 è uguale a 2 L’operatore modulo calcola il resto della

divisione: 13 % 5 è uguale a 3

• Precedenza degli operatori: Come in aritmetica, moltiplicazione e divisione

hanno priorità su addizione e sottrazione• si usano le parentesi quando c’è ambiguità

Per esempio: la media aritmetica di a, b, c: a + b + c / 3 NO !!!! (a + b + c ) / 3 SI

Aritmetica (1/2)Aritmetica (1/2)


34

Aritmetica (2/2)Aritmetica (2/2)Operazione Operatore C Espressione

aritmeticaEspressione C

Addizione + f+7 f + 7Sottrazione - p-c p – cMoltiplicazione * bm b * mDivisione / x/y x / yModulo % r mod s r % s

Operatori C Operazioni Precedenza

( ) Parentesi Valutate per prime. Se ci sono degli annidamenti, si valuta prima la coppia più interna. Se ci sono più coppie allo stesso livello, si valuta da sinistra a destra.

* , / , % Moltiplicazione, Divisione, Modulo

Valutate per seconde. Se ce ne sono diverse, si valutano da sinistra a destra.

+ , – Addizione, Sottrazione

Valutate per ultime. Se ce ne sono diverse, si valutano da sinistra a destra.


Fine, domande?Fine, domande?

35

Pausa Pausa 10’10’


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

36


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”

37


Pseudocodice vs Codice CPseudocodice vs Codice C

• Pseudocodice

1. Scrivi “quanto sei alto?”2. Leggi altezzacm3. Altezzam = alteccacm/1004. Scrivi “sei alto: altezzam”

38


Un primo errore Un primo errore

39


Un secondo erroreUn secondo errore

40


Un terzo erroreUn terzo errore

41


Soluzione correttaSoluzione corretta

42

L ’importanza dei tipi di dato


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

43


Mostra caratteriMostra caratteri

• Problema Si scriva un programma che richieda

l’inserimento di un carattere e lo mostri a video

44


Tipo carattere e codifica ASCIITipo carattere e codifica ASCII

45


Ricordate il Ricordate il ““-32-32””

46


Un esempio di calcolo Un esempio di calcolo

47


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

48


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

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Algoritmi e basi del C Marco D. Santambrogio –...

Documents

Transcript of DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Algoritmi e basi del C Marco D. Santambrogio –...