Informatica Generale
Marzia Buscemi
[email protected]
Ricevimento: Giovedì ore 16.00-18.00,
Dipartimento di Informatica, stanza 306-PS
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~buscemi/IG07.htm
(sommario delle lezioni in fondo alla pagina)
1
Argomenti trattati la scorsa
lezione
 Cos’è un programma
 Com’è organizzata la memoria nel
calcolatore (memoria centrale e memoria
di massa)
 Linguaggi di programmazione
 Linguaggio macchina
 Linguaggio assembler
 Linguaggi ad alto livello
 Variabili, costanti e tipi di dato
2
Cosa tratteremo in questa
lezione

Le strutture di controllo
sequenza di istruzioni
 selezione (if .. then .. else ..)
 iterazione (while .. do, repeat ..
while, for .. to .. do)


Come si rappresentano gli algoritmi:
pseudocodice
 diagramma di flusso


Le strutture dati

array
3
Istruzioni elementari
 Operazioni aritmetiche di base:
somma (a+b), sottrazione (a-b),
confronto (a=b oppure a==b)
 Operazioni di I/O: leggere da tastiera
(read a), scrivere sullo schermo (write
a)
 Operazioni di assegnamento (a :=
b+c oppure a=b+c)
4
Strutture di controllo 1
 Strutture di controllo:
sono comuni a tutti i tipi di linguaggi di
programmazione
 definiscono l’ordine in cui eseguire le
istruzioni di un programma
 si dividono in tre tipi fondamentali:
 sequenza di istruzioni
 selezione (if)
 ripetizione (for, while, repeat)

5
Strutture di controllo 2
 Sequenza: se S1, S2, ... , Sk sono istruzioni,
allora una sequenza è:
S1;
S2;
...
Sk;
 Le istruzioni sono eseguite in successione
ordinata.
 Esempi:
 culinario: “mettere farina, poi aggiungere
uova, ...”.
 linguaggio C:
{
x = y + 2;
z = x*4;
6
Strutture di controllo 3
 Selezione:



se E è vera allora S1 altrimenti S2
Indica la scelta tra due possibilità.
Se in un caso si vogliono eseguire istruzioni
in più si elimina il ramo “altrimenti”
Esempi:
 “se avete burro scioglietelo e poi
versatelo, altrimenti versate direttamente
l’olio.
 if (a>0)
a=a-1;
else
7
b=a;
Strutture di controllo 4
 Ciclo condizionato (for):
Esegui (S1, S2, ... , Sk) N volte
 Il ciclo (loop) viene eseguito n volte.
 Esempi:
“Prendere un uovo e separare il tuorlo dall’albume.
Ripetere l’operazione con altre 10 uova.”
 linguaggio C:
for (i=1; i <=100; i++) ad ogni ciclo
assegna a “i”
{
incrementa di 1
il valore 1
il valore di “i”
...
}

ripete il ciclo finché
vale questa condizione
8
Strutture di controllo 5
 Ciclo condizionato (while):
Finché E, esegui (S1, S2, ... , Sk)
 Il ciclo (loop) viene eseguito per tutto il tempo in
cui vale E.
 Esempi:
 “Finché non si è sciolto il burro, tenere il
tegame sul fuoco”
 linguaggio C: i= 1;
while (i <=100)
{
...
i++;
}
9
Algoritmi e programmi
Algoritmo
Codifica in un linguaggio di
programmazione (C, Java, etc)
Programma
Input : programma
Compilatore
Eseguibile
Output : rappresentazione comprensibile alla macchina
10
Algoritmi 1
 Algoritmo:






sequenza di azioni non ambigue che da un dato
input produce un output
dato un problema, descrive teoricamente la
sequenza di istruzioni che devono essere eseguite
per risolvere il problema
viene “scritto” in un certo linguaggio di
programmazione (implementazione)
Il flusso di istruzioni di un algoritmo e’ regolate
dalle stutture di controllo.
può essere rappresentato mediante pseucodice o
diagrammi di flusso
le informazioni sono organizzate in modo logico,
tramite le strutture di dati
11
Algoritmi 2
Ci sono due modi di rappresentare gli algoritmi.
 Lo pseudocodice:



“assomiglia” (pseudo) alla sintassi (codice)
usata nei linguaggi di programmazione
il flusso di istruzioni è rappresentato con
precisione
le istruzioni sono definite “informalmente”
 I diagrammi di flusso:
 sono grafici che permettono di esprimere un
algoritmo in modo preciso ed intuitivo
 si costruiscono a partire da blocchi “base” che
rappresentano le operazioni elementari ed i
costrutti di controllo
 i blocchi base sono collegati tramite “freccie”
12
Algoritmi: pseudocodice 1
 Lo pseudocodice sfrutta le parole chiave e l’indentazione.
 Esempio informale:
tipi di dato in input: latte, uova, ...
tipi di dato in output: torta
inizio preparazione
metti farina in una casseruola;
aggiungi lo zucchero;
se zucchero non basta vai a comprarlo;
...
finché il composto non si è amalgamato,
rimescola;
fine preparazione
13
Algorimi: pseudocodice 2
 Parole chiave (possono essere in
italiano, in inglese, etc.) e indentazione:





Inizio e fine programma: begin, end;
I/O: read (per leggere l’input), write,
return, print (per scrivere l’output),
Sequenza: successione di istruzioni con
la stessa indentazione
Selezione: if .. then .. else ..
Iterazione: while .. do, repeat .. until,
for .. to .. do
14
Algoritmi: pseudocodice 3
Esempio 1:
Esempio 2:
1. leggi i numeri x e y
2. assegna a d il
valore x – y
3. se d è maggiore di
zero allora scrivi x
altrimenti scrivi y
var d: int
più discorsivo
begin
read x, y;
d := x – y;
if d>0 then return x;
else return y;
end
più formale
15
Algoritmi: diagrammi di
flusso
 Sono grafici che permettono di esprimere un algoritmo in modo
preciso ed intuitivo
 Si costruiscono a partire da blocchi base che rappresentano le
operazioni elementari ed i costrutti di controllo
 I blocchi base sono collegati tramite ‘freccie’
blocco di istruzioni
sequenziali
operazioni
di I/O
condizione
inizio progr.
Es. if C then I else L
begin
no
C
fine progr.
yes
I
L
sottoprogramma
16
end
Esempi

1.
2.
3.
4.
Scrivere gli algoritmi in pseudocodice e
diagramma di flusso per risolvere i seguenti
problemi:
Dati x e y, scrivere un algoritmo che calcoli il
massimo tra x e y (usando solo sottrazione e
assegnamenti)
Calcolare il massimo tra 3 numeri
Calcolare il massimo tra N numeri
Scrivere un algoritmo che calcola il prodotto
di due interi x e y (usando solo somma e
assegnamenti)
17
Il maggiore fra 2 numeri
interi x, y
 Algoritmo max
1. Leggi i valori di x e y dall’esterno
2. Calcola la differenza d fra x e y (d=x-y)
3. Se d è maggiore di 0 vai al passo 5
altrimenti prosegui in sequenza
4. Stampa ‘il massimo è …’ seguito dal valore di
y e vai a 6
5. Stampa ‘il massimo è …’ seguito dal valore di
x
6. Termina l’esecuzione
18
Diagramma di flusso di max
Inizio
Passo 1
Leggi x e y
Passo 2
d=x-y
Si
Passo 3No
d>0?
Scrivi ‘max è y’
Scrivi ‘max è x’
Passo 5
Passo 4
Fine
Passo 6
19
Il maggiore fra 3 numeri
interi
 Possiamo sfruttare l’algoritmo max come
‘sottoalgoritmo’
 Algoritmo max_3
1. Leggi i valori di x, y, z dall’esterno
2. Valuta se x> y usando l’algoritmo max
3. In caso affermativo vai al passo 5
4. Trova il massimo fra y e z (con max) e
termina
5. Trova il massimo fra x e z (con max) e
termina
20
Il massimo fra N numeri
interi
 Possiamo ancora sfruttare l’algoritmo max
come ‘sottoalgoritmo’!
 Idea … trovare prima il maggiore fra i primi
due numeri, poi confrontare il risultato con il
terzo, poi con il quarto etc …
 In pratica, possiamo usare la struttura di
controllo iterativa while…do per effettuare le
operazioni di max su tutti i numeri in
ingresso
21
Determinare il massimo fra
N numeri interi
 Algoritmo max_N
1. Leggi il valore di N dall’esterno
2. Leggi i primi due numeri
3. Trova il maggiore m fra i primi due numeri
(con max)
4. Finchè (hai esaminato meno di N numeri)
a. Leggi un nuovo numero x
b. Trova il maggiore fra m e x usando l’algoritmo
max
c. Assegna il valore del maggiore a m
5. Stampa ‘il massimo è…’ ed il valore di m e
termina
22
Diagramma di flusso per il
problema del massimo di
N numeri
Inizio
Leggi i primi due numeri x1 e x2
e memorizzali nelle variabili a e b
m = max(a,b)
Si
Leggi il nuovo
numero in a
Ancora numeri
da esaminare ?
No
Scrivi ‘max è m’
Fine
m = max(a,m)
Supponiamo N fissato
23
Inizio
Leggi N
Leggi i primi due numeri x1 e x2
e memorizzali nelle variabili a e b
m = max(a,b)
Si
I=2
No
I<N?
I=I+1
Leggi il nuovo
numero in a
Scrivi ‘max è m’
Fine
DF per il problema del
massimo di N numeri
(versione più formale)
m = max(a,m)
Supponiamo N almeno 2
24
Prodotto di due interi positivi x
ey
 Algoritmo prod
1. Leggi i valori di x e y dall’esterno
2. Assegna a p il valore di 0. (p=0)
3. Se y è uguale a 0 vai al passo 5
4. Assegna a p il valore p+x (p=p+x)
5. Decrementa y di 1 (y=y-1) e vai al
passo 3
6. Stampa ‘il prodotto di x per y è … ’
seguito dal valore di p
7. Termina l’esecuzione
25
Strutture dati
 Tutti i linguaggi ad alto livello per la
programmazione permettono di definire due
tipi di aggregati di variabili (o strutture dati)


array : tabelline di valori tutti dello stesso tipo
record : gruppi di variabili di tipo diverso
 Le strutture dati seguono criteri logici e non
fisici.
 I compilatori traducono le istruzioni che
manipolano strutture dati in istruzioni che
operano su locazioni di memoria.
26
Array

1

Possiamo definire una sequenza lunga N
es.
3
7
Array di 4 valori interi (a una sola dimensione)
8
Possiamo definire una tabella a due
dimensioni, ad esempio per memorizzare
le vendite di un prodotto in un trimestre
dell’anno
I
II
III
Prod 1
1
32
7
8
Prod 2
9
3
3
8
Prod 3
14
3 723 82
IV
Array 3x4 di 12 valori interi (a due dimensioni)
27
Array 2
 Come si specifica la struttura di un array? E
come si usano le singole variabili nella
struttura?
 La struttura si specifica con il tipo e
l’ampiezza di ogni dimensione

es :
1


3
7
8
int X[4]
int T[3][4]
Nomi delle tabelle
I
II
III
Prod 1
1
32
7
8
Prod 2
9
3
3
8
Prod 3
14
3 723 82
IV
28
Array 3
 Uso di una singola variabile :


Si specificano le coordinate della variabile desiderata
Ogni elemento di ogni dimensione è identificato da
un valore da 1 a N (o da 0 a N-1, dipende dal
linguaggio)
Noi generalmente seguiremo la
convenzione del linguaggio C di
partire da 0
0
1
2
3
1
3
7
8
valore
I
II
III
Prod 1
1
32
7
8
Prod 2
9
3
3
8
Prod 3
14
3 723 82
X[1]
T[1][0]
posizione
IV
29
Esempi
 Dato un array A di interi di lunghezza N e un valore
(chiave) k, scrivere un algoritmo Calc_Posiz_k
(A,N) che dà in output l’indice i tale che A[i]=k.
Es.:
A
3
0
9
1
6
5
2
3
Calc_Posiz_9(A,4)
dà in output i=1
 Suggerimento: provare prima usando for poi
usando while.Confrontare le soluzioni.
30
Esercizio proposto
 Dato un array A di lunghezza N,
scrivere un algoritmo palindromo_N che
restituisce in output True se A è
palindromo, False altrimenti.
N.B. Una sequenza di numeri (o
caratteri) è palindroma se, letta al
rovescio, rimane identica. Es.:
A=011110, A=anna.
31