Laboratorio di Informatica 1
Parte 5
Laboratorio di InformaticaDott.ssa Elisa TiezziDott.ssa Elisa Mori
Laboratorio di Informatica 2
Programmazione
• Concetti base:– dati– istruzioni
• Dati:– variabili– tipi
• Istruzioni: – istruzioni base– strutture di controllo– sotto-programmi
Laboratorio di Informatica 3
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
Laboratorio di Informatica 4
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
Laboratorio di Informatica 5
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
Laboratorio di Informatica 6
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();
Laboratorio di Informatica 7
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;
}
Laboratorio di Informatica 8
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
Laboratorio di Informatica 9
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
Laboratorio di Informatica 10
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
Laboratorio di Informatica 11
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
Laboratorio di Informatica 12
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
Laboratorio di Informatica 13
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
Laboratorio di Informatica 14
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
Laboratorio di Informatica 15
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
Laboratorio di Informatica 16
Scomporre e comporre• Principio del divide et impera
• Suddividere per isolare parti il più possibile autonome ed indipendenti
• Parti potenzialmente riutilizzabili
Laboratorio di Informatica 17
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
Laboratorio di Informatica 18
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
Laboratorio di Informatica 19
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
Laboratorio di Informatica 20
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
Laboratorio di Informatica 21
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
Laboratorio di Informatica 22
Struttura di un programma• Procedura principale
• Più procedure a servizio di quella principale
• Ciascuna di quest’ultime, a sua volta, ne può usare altre
Laboratorio di Informatica 23
Una visione graficaproceduraprincipale
proceduraasservita P1
proceduraasservita P2
proceduraasservita P4
proceduraasservita P3
A BA usa B
proceduraasservita P5
Laboratorio di Informatica 24
Realizzazione in Java
• Procedura principale– procedura main
• Per ciascuna procedura asservita– interfaccia
• dichiarazione
– implementazione• definizione del corpo
Laboratorio di Informatica 25
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
Laboratorio di Informatica 26
Struttura (parziale)main
isApparent isProper isFETS isFBTS computeRN computeRD
computeGCD
Laboratorio di Informatica 27
Frazioni apparenti e proprie
boolean isApparent(int n, int d){return (n % d == 0);
}
boolean isProper(int n, int d){return (n < d);
}
Laboratorio di Informatica 28
Confronto tra frazioniboolean 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);
}
Laboratorio di Informatica 29
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;
}
Laboratorio di Informatica 30
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));
}
Laboratorio di Informatica 31
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);
...
}
Laboratorio di Informatica 32
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;
}
Laboratorio di Informatica 33
Algoritmo di Euclide
• Proprietà:– se r è il resto della divisione di a per b (ab), 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)
Laboratorio di Informatica 34
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;
}
Laboratorio di Informatica 35
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
Laboratorio di Informatica 36
Ricorsione in matematica
• Le formule matematiche sono spesso espresse in termini ricorsivi
• Esempio: definizione di fattoriale
1!=1
N!=N * (N-1)!
Laboratorio di Informatica 37
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
Laboratorio di Informatica 38
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
Laboratorio di Informatica 39
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)
Laboratorio di Informatica 40
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
Laboratorio di Informatica 41
Implementazione ricorsiva
int computeFib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return computeFib(n-1)+computeFib(n-2);
}
Laboratorio di Informatica 42
1 0
21
1 0
Numero di invocazioni
• Numero totale di invocazioni cresce esponenzialmente
1 0
21
32
43
5
Laboratorio di Informatica 43
Implementazione iterativaint computeFib(int n){int i = 1, x = 1, y = 0;while (i < n) {
i = i+1;x = x+ y;y = x -y;
}return x;
}
Laboratorio di Informatica 44
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
Laboratorio di Informatica 45
Le torri di Hanoiinventato 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
Laboratorio di Informatica 46
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
Laboratorio di Informatica 47
Implementazione 1void 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);
}
}
Top Related