Parte 5
Fondamenti di Programmazione
1
Programmazione
• Concetti base:
 dati
 istruzioni
• Dati:
 variabili
 tipi
• Istruzioni:
 istruzioni base
 strutture di controllo
 sotto-programmi
2
Sotto-programmi
• Necessità di scomporre programmi complessi
• Sotto-programma: insieme di istruzioni a cui è dato un
nome
• il nome usato come sostituto dell’intero insieme di istruzioni
• Esempio
 generare un numero intero casuale compreso tra 1 e 100
• raggruppare le necessarie istruzioni in un sotto-programma di nome
randomNumber
• ogni volta che il programma deve generare un numero intero casuale
compreso tra 1 e 100, lo può fare con una semplice istruzione:
randomNumber()
• Vantaggi:
• risparmio di scrittura, organizzazione, riutilizzo
3
Sotto-programmi in Java
• In Java, i sotto-programmi sono chiamati
metodi
• Interfaccia (sintattica) di un metodo:
 nome del metodo
 input richiesto
 output fornito
• Sintassi della dichiarazione:
Tipo_Output Nome_Metodo(Lista_Input)
Blocco // corpo del metodo
4
Tipologie di metodi
• Alcuni metodi (talvolta, detti funzioni) eseguono
un’azione e ritornano un singolo valore
 esempio: il metodo randomNumber genera un
numero intero casuale compreso tra 1 e 100 e ne ritorna
il valore
• Altri metodi (talvolta, detti procedure) si limitano
ad eseguire un’azione
 esempio: il metodo printWelcomeMessage stampa
un messaggio di benvenuto
5
Tipo di ritorno dei metodi
• Sempre specificato
• Può essere:
 tipo di dato primitivo (come char oppure
int)
 classe (come String)
 void se nessun valore viene ritornato
• Un metodo (non void) può essere usato
ovunque è lecito usare il suo tipo di ritorno
 esempio:
int r = randomNumber();
6
Istruzione return
• I metodi che ritornano un valore devono eseguire,
all’interno del corpo, un’istruzione return che
include il valore da ritornare
• Esempio:
int randomNumber()
{
int r = 1+(int)(Math.random()*99);
return r;
}
7
Esempio di metodo void
• Definizione del metodo
printWelcomeMessage:
void printWelcomeMessage()
{
System.out.println(``Hello!’’);
System.out.println(``Welcome to paradise!’’);
}
• Questo metodo esegue un’azione (stampa
un messaggio di benvenuto) ma non ritorna
alcun valore
8
Nomi di metodi
• Buone regole di programmazione:
 verbi per nominare metodi senza un valore di ritorno
• realizzano un azione
• esempio: printIntegerNumber
 nomi per nominare metodi con un valore di ritorno
• creano (ritornano) un dato, ovvero una cosa
• esempio: randomNumber
 iniziare il nome di un metodo con una lettera minuscola
9
Parametri di un metodo
• Metodi più flessibili (e quindi più utili) con valori
di input (detti valori passati o parametri)
• Parametri e loro tipi di dato specificati all’interno
delle parentesi tonde successive al nome del
metodo
 questi sono i parametri formali
• lista di parametri separati da virgole
• Invocando un metodo, vanno inseriti (all’interno
delle parentesi tonde) valori del tipo specificato e
nell’ordine specificato
 questi sono gli argomenti, o parametri attuali
10
Esempio
• Dichiarazione:
int randomNumber(int min, int max)
{
return min+(int)(Math.random()*(max-min));
}
 parametri formali: min e max
• Invocazione:
int m = 10;
int M = 20;
int r = randomNumber(m, M);
 argomenti: m ed M
11
Passaggio per valore
• Parametri formali sono locali al loro metodo
 variabili usate come argomenti non possono essere modificate dal
metodo
• metodo riceve solo il loro valore
• Quando un metodo è invocato, il valore di ciascun
argomento è copiato nel (assegnato al) corrispondente
parametro formale
 numero di argomenti uguale a numero di parametri formali
 tipo di dati degli argomenti uguale a quello dei corrispondenti
parametri formali
 parametri formali inizializzati con i valori passati
12
Variabili locali ad un blocco
• Variabile dichiarata all’interno di un blocco:
 vista solo all’interno del blocco
• locale al blocco, per cui è chiamata variabile locale
• se il blocco è il corpo di un metodo, la variabile è detta essere
una variabile locale del metodo
 quando il blocco termina l’esecuzione, le variabili locali
spariscono
• riferimenti a variabili locali fuori del blocco corrispondente
causano errori di compilazione
• Variabile dichiarata nell’inizializzazione di un
for è locale al ciclo for
 non può essere usata fuori del ciclo
13
Quando e dove
• Dichiarare una variabile fuori di tutti i blocchi ma
all’interno di un metodo la rende disponibile a tutti
i blocchi del metodo
• Buone regole di programmazione
 dichiarare le variabili immediatamente prima di
utilizzarle
 inizializzare le variabili al momento della dichiarazione
 non dichiarare variabili all’interno di cicli
• richiede tempo la creazione e la distruzione di una variabile
• eccezione: variabili dichiarate nell’inizializzazione di un ciclo for
14
Programmazione
procedurale
• Obiettivo
 Concepire la costruzione di programmi di grande
dimensione e complessità come composizione di
componenti (procedure)
• costruite ad hoc
• esistenti
• Vantaggi
 dominare la complessità
 ridurre i costi
 aumentare parallelismo nello sviluppo
15
Scomporre e comporre
• Principio del divide et impera
• Suddividere per isolare parti il più possibile
autonome ed indipendenti
• Parti potenzialmente riutilizzabili
16
Autonomia ed indipendenza
• Ogni parte deve avere una sua coesione da
un punto di vista logico
 deve rappresentare un’astrazione significativa
• Ogni parte deve essere il più possibile
indipendente dalle altre parti
17
Procedura
• È una parte del sistema complessivo
• Deve avere, rispetto alle altre parti,
un’interfaccia ben definita
 interfaccia: tutto ciò che è necessario conoscere
per poter usare la procedura
18
Procedure e metodi
• Un metodo Java può essere considerato
come una procedura
• La sua interfaccia è specificata
nell’intestazione
• È bene che non modifichi variabili che non
sono locali
 indipendenza dalle altre procedure
19
Relazione di utilizzo
• Procedura A usa procedura B se, per
svolgere il proprio compito, deve accedere
alla procedura B attraverso quanto definito
nell’interfaccia di quest’ultima
 esempio: se il metodo F invoca il metodo G,
allora F usa G
20
Interfaccia/implementazione
• Occorre distinguere tra questi due aspetti
• Interfaccia
 dice ciò che le altre procedure possono
conoscere
• Implementazione
 è come ciò che viene offerto attraverso
l’interfaccia è effettivamente realizzato
21
Struttura di un programma
• Procedura principale
• Più procedure asservite a quella principale
• Ciascuna di quest’ultime, a sua volta, ne
può usare altre
22
Una visione grafica
A usa B
A
B
procedura
asservita P1
procedura
asservita P5
procedura
principale
procedura
asservita P2
procedura
asservita P3
procedura
asservita P4
23
Realizzazione in Java
• Procedura principale
 procedura main
• Per ciascuna procedura asservita
 interfaccia
• dichiarazione
 implementazione
• definizione del corpo
24
Esempio
• Programma che genera due frazioni
• Decide se sono
 apparenti: numeratore multiplo di denominatore
 proprie: numeratore minore di denominatore
•
•
•
•
Confronta le due frazioni
Riduce le due frazioni ai minimi termini
Riduce le due frazioni allo stesso denominatore
Esegue le quattro operazioni
25
Struttura (parziale)
main
isApparent
isProper
isFETS
isFBTS
computeRN
computeRD
computeGCD
26
Frazioni apparenti e proprie
boolean isApparent(int n, int d)
{
return (n % d == 0);
}
boolean isProper(int n, int d)
{
return (n < d);
}
27
Confronto tra frazioni
boolean isFETS(int n1,int d1,int n2,int d2)
{
return (n1*d2 == n2*d1);
}
boolean isFBTS(int n1,int d1,int n2,int d2)
{
return (n1*d2 > n2*d1);
}
28
Calcolo del MCD (1)
int computeGCD(int n, int d){
int count = 2, min = n, GCD = 1;
if (n > d) min = d;
while (count <= min) {
if ((n%count == 0) && (d%count == 0))
GCD = count;
++count;
}
return GCD;
}
29
Semplificazione di frazioni
int computeRN(int n, int d)
{
return (n / computeGCD(n, d));
}
int computeRD(int n, int d)
{
return (d / computeGCD(n, d));
}
30
Procedura principale
void main()
{
int n1 = 1+(int)(Math.random()*99);
int d1 = 1+(int)(Math.random()*99);
int n2 = 1+(int)(Math.random()*99);
int d2 = 1+(int)(Math.random()*99);
...
}
31
Calcolo del MCD (2)
int computeGCD(int n, int d){
int GCD = n;
if (n > d) GCD = d;
while (GCD > 1) {
if ((n%GCD == 0) && (d%GCD == 0))
break;
--GCD;
}
return GCD;
}
32
Algoritmo di Euclide
• Proprietà:
 se r è il resto della divisione di a per b (ab),
allora i divisori comuni di a e b coincidono con
quelli di b ed r
 MCD(a, b) = MCD(b, r) dove r = a mod b
• Algoritmo:
 se b=0, allora MCD(a, b) = a, altrimenti
MCD(a, b) = MCD(b, a mod b)
33
Calcolo del MCD (3)
int computeGCD(int n, int d)
{
int temp = 0;
while (d > 0) {
temp = d;
d = n % d;
n = temp;
}
return n;
}
34
Ricorsione
• Strumento potente per definizioni
matematiche
• Possibilità di definire insieme infinito di
oggetti con regola finita
 possibilità di descrivere un insieme infinito di
computazioni con un programma finito
35
Ricorsione in matematica
• Le formule matematiche sono spesso
espresse in termini ricorsivi
• Esempio: definizione di fattoriale
1!=1
N!=N * (N-1)!
36
Metodi ricorsivi
• Contengono riferimenti espliciti a sé stessi
 direttamente ricorsivi
• Un metodo ne invoca un altro e
l’esecuzione di quest’ultimo porta ad un
certo punto ad invocare nuovamente
(direttamente o indirettamente) il metodo
originale
 indirettamente ricorsivi
37
Ricorsione infinita
• Requisito fondamentale:
 chiamata ricorsiva subordinata ad una condizione che
ad un certo istante deve divenire non soddisfatta
• Qualsiasi definizione ricorsiva deve avere
una parte non ricorsiva, detta base della
ricorsione, che permette alla ricorsione
stessa di terminare
• Nell’esempio precedente del fattoriale la
base è 1! che è posto uguale ad 1
38
Variabili in metodi ricorsivi
• Ogni invocazione genera un nuovo insieme
di variabili locali
• Ogni parametro riceve un valore iniziale in
base alla nuova invocazione
• Ogni volta che il metodo termina si ritorna
al metodo che lo ha chiamato ( che potrebbe
essere lo stesso)
39
Numeri di Fibonacci
• Schema più complicato di composizione
ricorsiva che potrebbe (e dovrebbe) essere
tradotto in forma iterativa
• Definizione:
 fib0 = 0
 fib1 = 1
 fibn+1 = fibn + fibn-1
40
Implementazione ricorsiva
int computeFib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return computeFib(n-1)+computeFib(n-2);
}
41
Numero di invocazioni
5
4
3
2
3
2
1
1
2
1
1
0
1
0
0
• Numero totale di invocazioni cresce
esponenzialmente
42
Implementazione iterativa
int computeFib(int n)
{
int i = 1, x = 1, y = 0;
while (i < n) {
i = i+1;
x = x+ y;
y = x -y;
}
return x;
}
43
Considerazioni
• Ricorsione deve essere evitata se esiste una
soluzione iterativa ovvia
• Non vuol dire evitare la ricorsione a
qualunque costo
 esistono molte buone applicazioni della
ricorsione
 algoritmi per loro natura ricorsivi vanno
implementati con metodi ricorsivi
44
Le torri di Hanoi
inventato nel 1880 da Lucas
• Tre aste (o torri) ed n dischi di dimensioni diverse
(con buco per inserirli nelle aste)
• All’inizio tutti i dischi sono nell’asta 1
 in ordine decrescente di grandezza
• Obiettivo: portarli nella torre 3 rispettando le
regole seguenti




nessun disco mai sopra uno più piccolo
si può spostare un solo disco alla volta
dischi sempre collocati su una torre (non a parte)
solo disco in cima ad una torre può essere spostato
45
Algoritmo ricorsivo
• Obiettivo: spostare k dischi da torre 1 a
torre 3
• Algoritmo:
 Spostare k-1 dischi da torre 1 a torre 2
 Spostare 1 disco da torre 1 a torre 3
 Spostare k-1 dischi da torre 2 a torre 3
46
Implementazione 1
void moveTowers(int k, int o,int d)
{
if (k > 0)
{
moveTowers(k-1, o, 6-o-d);
System.out.println("Sposta da "+o+"a"+d);
moveTowers(k-1,6-o-d,d);
}
}
47