1

Parte 5

Fondamenti di Programmazione

2

Programmazione

• Concetti base: dati istruzioni

• Dati: variabili tipi

• Istruzioni: istruzioni base strutture di controllo sotto-programmi

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

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

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

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

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;

}

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

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

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

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

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

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

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

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

16

Scomporre e comporre

• Principio del divide et impera

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

• Parti potenzialmente riutilizzabili

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

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

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

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

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

22

Struttura di un programma

• Procedura principale

• Più procedure asservite a quella principale

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

23

Una visione grafica

proceduraprincipale

proceduraasservita P1

proceduraasservita P2

proceduraasservita P4

proceduraasservita P3

A BA usa B

proceduraasservita P5

24

Realizzazione in Java

• Procedura principale procedura main

• Per ciascuna procedura asservita interfaccia

•dichiarazione

implementazione•definizione del corpo

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

26

Struttura (parziale)

main

isApparent isProper isFETS isFBTS computeRN computeRD

computeGCD

27

Frazioni apparenti e proprie

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

}

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

}

28

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

}

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;

}

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

}

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

...

}

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;

}

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)

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;

}

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

36

Ricorsione in matematica

• Le formule matematiche sono spesso espresse in termini ricorsivi

• Esempio: definizione di fattoriale

1!=1 N!=N * (N-1)!

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

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

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)

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

41

Implementazione ricorsiva

int computeFib(int n)

{

if (n == 0)

return 0;

if (n == 1)

return 1;

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

}

42

1 0

21

1 0

Numero di invocazioni

• Numero totale di invocazioni cresce esponenzialmente

1 0

21

32

43

5

43

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;

}

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

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

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

47

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

}