Laboratorio di Informatica1 Parte 5 Laboratorio di Informatica Dott.ssa Elisa Tiezzi Dott.ssa Elisa...

Laboratorio di Informatica 1

Parte 5

Laboratorio di InformaticaDott.ssa Elisa TiezziDott.ssa Elisa Mori


Programmazione

• Concetti base:– dati– istruzioni

• Dati:– variabili– tipi

• Istruzioni: – istruzioni base– strutture di controllo– sotto-programmi


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


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


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


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();


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;

}


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


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


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


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


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


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


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


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


Scomporre e comporre• Principio del divide et impera

• Suddividere per isolare parti il più possibile autonome ed indipendenti

• Parti potenzialmente riutilizzabili


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


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


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


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


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


Struttura di un programma• Procedura principale

• Più procedure a servizio di quella principale

• Ciascuna di quest’ultime, a sua volta, ne può usare altre


Una visione graficaproceduraprincipale

proceduraasservita P1




A BA usa B



Realizzazione in Java

• Procedura principale– procedura main

• Per ciascuna procedura asservita– interfaccia

• dichiarazione

– implementazione• definizione del corpo


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


Struttura (parziale)main

isApparent isProper isFETS isFBTS computeRN computeRD

computeGCD


Frazioni apparenti e proprie

boolean isApparent(int n, int d){return (n % d == 0);

}

boolean isProper(int n, int d){return (n < d);

}


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);

}


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;

}


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));

}


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);

...

}


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;

}


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)


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;

}


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


Ricorsione in matematica

• Le formule matematiche sono spesso espresse in termini ricorsivi

• Esempio: definizione di fattoriale

1!=1

N!=N * (N-1)!


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


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


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)


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


Implementazione ricorsiva

int computeFib(int n)

{

if (n == 0)

return 0;

if (n == 1)

return 1;

return computeFib(n-1)+computeFib(n-2);

}


1 0

21

1 0

Numero di invocazioni

• Numero totale di invocazioni cresce esponenzialmente

1 0

21

32

43

5


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;

}


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


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


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


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);

}

}

Laboratorio di Informatica1 Parte 5 Laboratorio di Informatica Dott.ssa Elisa Tiezzi Dott.ssa Elisa...

Documents

Transcript of Laboratorio di Informatica1 Parte 5 Laboratorio di Informatica Dott.ssa Elisa Tiezzi Dott.ssa Elisa...