Corso: FondamentiFondamenti di di Programmazione Programmazione

Classe: PARI-DISPARI

Docente: Prof. Luisa Gargano

Testo: Aho, Ulman, Foundations of Computer Science –C Edition W.H. Freeman and Company, NY, 1994

Finalita’: introduzione alla programmazione

Concetti introduttiviConcetti introduttivi

CalcolatoreCalcolatore: “Oggetto” in grado di 1) accedere a grandi quantita’ di informazioni 2) eseguire un insieme di operazioni elementari (es. aritmetiche) in modo preciso e rapido

ProgrammazioneProgrammazione: Lavoro che si fa per costruire sequenze di istruzioni (operazioni) adatte a svolgere il calcolo “desiderato”

Concetti introduttiviConcetti introduttivi

CalcolatoreCalcolatore: “Oggetto” in grado di 1) accedere a grandi quantita’ di informazioni 2) eseguire un insieme di operazioni elementari (es. aritmetiche) in modo preciso e rapido

ProgrammazioneProgrammazione: Lavoro che si fa per costruire sequenze di istruzioni (operazioni) adatte a svolgere il calcolo “desiderato”

AlgoritmoAlgoritmo: Sequenza di azioni per svolgere il calcolo

INPUT: dati iniziali INPUT: x,y,z

AZIONI esempio: Somma x ed y Somma z al risultato

OUTPUT: risultato OUTPUT: x+y+z

ALGORITMI e PROGRAMMIALGORITMI e PROGRAMMI

AlgoritmoAlgoritmo: Sequenza di azioni per svolgere il calcolo

INPUT: dati iniziali INPUT: x,y,z

AZIONI esempio: Somma x ed y Somma z al risultato

OUTPUT: risultato OUTPUT: x+y+z

ProgrammaProgramma: Algoritmo espresso in notazione formale (linguaggio di programmazione)

Creazione programma: Creazione programma: Fase 1 = algoritmo Fase2 = implementazione in dato linguaggio (C)

SCOPO del CORSO: SCOPO del CORSO: metodi di costruzione di algoritmi e programmi

Introduzione al linguaggio CIntroduzione al linguaggio C

IstruzioneIstruzione: Descrizione formale di un’azione

esempio: Moltiplica due numeri, indica il prodotto con z

Per ogni coppia di numeri il programma deve descrivere il processo di moltiplicarli

input: 3, 4 Output: z = 12 input: 2, 9 Output: z = 18

Introduzione al linguaggio CIntroduzione al linguaggio C

IstruzioneIstruzione: Descrizione formale di un’azione

esempio: Moltiplica due numeri, indica il prodotto con z

Per ogni coppia di numeri il programma deve descrivere il processo di moltiplicarli

input: 3, 4 Output: z = 12 input: 2, 9 Output: z = 18

VariabiliVariabili: Non si usano numeri, ma NOMI che denotano oggetti dal valore variabile All’inizio del programma bisogna assegnare i valori alle variabiliesempio: Moltiplica due numeri, indica il prodotto con z variabili: x,y,z x,y prendono i valori input

z assume il valore output

Introduzione al linguaggio CIntroduzione al linguaggio C

Assegnamento Assegnamento di un valore v ad una variabile x denotato con x=v

Il valore v puo’ anche essere il valore assunto da un’altra variabile o combinazioni di variabiliEsempio: z=x* y x ha valore 3, y ha valore 4 z assume valore 12

EspressioniEspressioni

Espressione: Espressione: formula (regola di calcolo) che specifica sempre un valoreEsempio: espressione algebrica: z=x* y, (x+3)/5

EspressioniEspressioni

Espressione: Espressione: formula (regola di calcolo) che specifica sempre un valoreEsempio: espressione algebrica: z=x* y, (x+3)/5

Espressione composta da: Operatori Operandi (costanti,

variabili,…)

EspressioniEspressioni

Espressione: Espressione: formula (regola di calcolo) che specifica sempre un valoreEsempio: espressione algebrica: z=x* y, (x+3)/5

Espressione composta da: Operatori Operandi (costanti,

variabili,…)

Operatori Algebrici: Operatori Algebrici: +, -, *, /, - unario, ++, --, %+, -, *, /, - unario, ++, --, % ( i%j= i modulo j= resto di i ( i%j= i modulo j= resto di i

diviso j)diviso j)

EspressioniEspressioni

Espressione: Espressione: formula (regola di calcolo) che specifica sempre un valoreEsempio: espressione algebrica: z=x* y, (x+3)/5

Espressione composta da: Operatori Operandi (costanti,

variabili,…)

Operatori Algebrici: Operatori Algebrici: +, -, *, /, - unario, ++, --, %+, -, *, /, - unario, ++, --, % ( i%j= i modulo j= resto di i ( i%j= i modulo j= resto di i

diviso j)diviso j)

Operatori Logici: Operatori Logici: AND (&&), OR (||), NOT (!), AND (&&), OR (||), NOT (!), (su variabili booleane - valore (su variabili booleane - valore vero/falso)vero/falso) x AND y VERO se e solo se x,y VEREx AND y VERO se e solo se x,y VERE

x OR y FALSO se e solo se x,y FALSEx OR y FALSO se e solo se x,y FALSE NOT x VERO se e solo se x FALSANOT x VERO se e solo se x FALSA

EspressioniEspressioni

Operatori di confronto: Operatori di confronto: Uguale “==“:Uguale “==“: x==yx==y da VERO sse da VERO sse x x e e yy hanno hanno stesso valore stesso valore

Diverso “!=“: Diverso “!=“: x!=y da x!=y da VERO sse VERO sse x e y x e y hanno dalori hanno dalori diversidiversi

Minore “<“Minore “<“

Minore o Uguale “<=“Minore o Uguale “<=“

Maggiore “>”Maggiore “>”

Maggiore o uguale “>=“Maggiore o uguale “>=“

ISTRUZIONIISTRUZIONI

AssegnamentoAssegnamento:: x=E, Calcola il valore dell’espressione E e lo assegna alla variabile x Esempio: x=x+y calcola il valore di x+y e lo assegna ad x

se x vale 5 e y vale 3, x=x+y da ad x valore 8

ISTRUZIONIISTRUZIONI

AssegnamentoAssegnamento:: x=E, Calcola il valore dell’espressione E e lo assegna alla variabile x Esempio: x=x+y calcola il valore di x+y e lo assegna ad x

se x vale 5 e y vale 3, x=x+y da ad x valore 8

Istruzioni Strutturate:Istruzioni Strutturate: 1) Composizione di Istruzioni1) Composizione di Istruzioni:

;I

;

;

m

2

1

I

IEsegui I1, quando e’ terminataesegui I2, quando e’ terminata…esegui Im.

x=1; y=2; x=x+y; (x vale 3) y=x*y (y vale 6)

ISTRUZIONI StrutturateISTRUZIONI Strutturate

2) Istruzioni Condizionali2) Istruzioni Condizionali:

If (C) I’ else I’’; C condizione, I’ ed I’’ composizioni di istruzioni

Es. Poni z=0 se x<=y; poni z=x-y se x>y if (x<=y) z=0 else x=x-y

ISTRUZIONI StrutturateISTRUZIONI Strutturate

2) Istruzioni Condizionali2) Istruzioni Condizionali:

If (C) I’ else I’’; C condizione, I’ ed I’’ composizioni di istruzioni

Es. Poni z=0 se x<=y; poni z=x-y se x>y if (x<=y) z=0 else x=x-y

Poni z=0 se x<=y; altrimenti lascia il valore di z inalterato if (x<=y) z=0

If (C) I;

Istruzioni RipetitiveFor (x=1, x<=n, x++) I; I e’ una composizione di istruzioni

Poni x=1 esegui IModifica x (x=2), esegui I…Modifica x (x=n), esegui I

y=0; for (x=1, x<=n, x++) y=y+x;

x y

0

1 1

2 1+2=3

3 1+2+3=6

… …

n 1+2+…+n

x=1

I

x++

X>nVero, ESCI

Falso

while ( C ) I; C e’ una condizione, I e’ una composizione di istruzioni

x=1; y=0; while (x<=n) {y=y+x; x++}

x y

0

1 1

2 1+2=3

3 1+2+3=6

… …

n 1+2+…+n

I

CFalso, ESCI

Vero

do I while (C);

x=1;y=0;do y=y+x; x++ while (x<=n)

y x

0 1

1 2

1+2=3 3

1+2+3=6 4

… …

1+2+…+n n+1 (>n)

I

CFalso, ESCI

Vero

n=0?

Risolvere problema

Scegliere astrazione: definire un Insieme di dati che rappresentano la realta’ (modello di dati)

Scegliere rappresentazione dellainformazione (struttura dati)

Algoritmo e programma

Es. Archivio impiegati contiene insieme di dati rilevanti (astrazione) su ogni impiegato

Rilevanti: Nome, stipendio, mansione Non rilevanti: altezza, peso, colore occhi, colore capelli

Tipi di dati

Principio di base: Programma ha accesso a

Scatole (box): ogni box ha associato un tipo (intero, reale,…) si possono conservare solo oggetti di tale tipo

Nome: ogni box e’ identificata da un nome

Tipi Base (in C): intero (int), reale (real), carattere (char)

Definizioni di variabili int x definisce x come variabile di tipo intero

Definizioni di Variabili

ARRAY formato da componenti dello stesso tipo le componenti sono individuate da un indice

int A[n] :array di n componenti di tipo intero

A[0] A[1] A[2] … A[n-1]

Si accede ad una componente alla volta specificando l’indice

int X[5]

X[0]=10;X[1]=7;X[2]=4;X[3]=3;X[4]=8;

Crea l’array di interi X:

10 7 4 3 8

Array

Es. cerca il minimo indice i di una componente di un array A[n] avente valore w.

idea: confronta w con A[0], A[1],… finche’ non trovi w oppure non hai esaminato tutto l’array

int A[n] i=0; while (A[i]!=w) && (i < n) i++; if(i==n) ‘’non esiste’’ /* altrimenti i contiene l’indice cercato*/

A[0] A[1] A[2] … A[n-1]

i=0A[0]=w esci

Array

Es. cerca il minimo indice i di una componente di un array A[n] avente valore w.

idea: confronta w con A[0], A[1],… finche’ non trovi w oppure non hai esaminato tutto l’array

int A[n] i=0; while (A[i]!=w) && (i < n) i++; if(i==n) ‘’non esiste’’ /* altrimenti i contiene l’indice cercato*/

A[0] A[1] A[2] … A[n-1]

A[0]!=w i=1 se A[1]=w esci

Array

Es. cerca il minimo indice i di una componente di un array A[n] avente valore w.

idea: confronta w con A[0], A[1],… finche’ non trovi w oppure non hai esaminato tutto l’array

int A[n] i=0; while (A[i]!=w) && (i < n) i++; if(i==n) ‘’non esiste’’ /* altrimenti i contiene l’indice cercato*/

A[0] A[1] A[2] … A[n-1]

A[0]!=w A[1]!=w A[2]!=w … i=n-1 se A[i]=w, esci altr. i++, esci con i=n

STRUCT

Permette di “unire” elementi di tipi differenti.

Es. Vogliamo descrivere persone usando 3 campi: (NOME, COGNOME, DATA-NASCITA)

Struct S{T1 M1; T2 M2; … Tn Mn}

Definisce una struttura con n campi (M1, M2, …, Mn)Di tipo T1,T2,…,Tn, rispettivamente.

STRUCT

Es. Vogliamo descrivere persone usando 3 campi: (NOME, COGNOME, DATA-NASCITA)

1) typedef char alfa[10] definisce il tipo alfa come un array di 10 caratteri

2) Struct data {int giorno; int mese; int anno}

3) Struct persona {alfa cognome; alfa nome; data data-nascita}

Struct persona P

P= (Mario, Rossi,(10,3,1980))

STRUCT

Es. Struct persona P= (Mario, Rossi,(10,03,1980)) P.nome e’ l’array contenete Mario P.nome[1] e’ il carattere a

P.data-nascita e’ la struttura di tipo data (10,3,1980)

P.data-nascita.mese e’ l’intero 3

La componente i-ma di nome Mi della struttura S, S=(M1,…,Mi,…,Mn), si indica con S.Mi

Es. Array di struct di tipo persona

persona A[n] array di n componenti A[0],…,A[i],…,A[n-1] A[i] e’ una struct di tipo persona

E’ possibile combinare array e strutture

Es. Array di struct di tipo persona

persona A[n] array di n componenti A[0],…,A[i],…,A[n-1] A[i] e’ una sruct di tipo persona

Cerca il numero di persone nate a maggio

{int count; count=0; for(i=0,i<n,i++) if (A[i].data.mese=5) count++;}

E’ possibile combinare array e strutture

Una variabile di tipo puntatore contiene un indirizzo di memoria

int x *p

Definisce p come un puntatore alla variabile di tipo intero x

PUNTATORI

P x

Una variabile di tipo puntatore contiene un indirizzo di memoria

int x *p

definisce p come un puntatore alla variabile di tipo intero x

P=&x assegna a p l’indirizzo di memoria di x

y=*p assegna a y il contenuto della variabile puntata da p

Es. {p=&x; y=*p} risulta valore di x = valore di y

PUNTATORI

Programma

Creazione di un programma

Algoritmo (metodo)

Implementazione in linguaggio dato

test