Esercizi sull'unità 10

Fondamenti di Informatica 1
Corso di Laurea in Ingegneria Informatica
Canale G-O, A.A. 2002/03

Esercitazione 10

Ricorsione

Esercizio 10A

Seguire l'evoluzione della pila dei record di attivazione usando il debugger di BlueJ per il programma Fibonacci.java. Per fare ciò, procedere come segue:

salvare il programma in una cartella del disco locale;
aprire tale cartella come progetto in BlueJ (usando il comando Open Non BlueJ);
compilare la classe Fibonacci;
aprire il file Fibonacci.java e mettere un breakpoint alla linea 17 (prima istruzione del metodo main); per mettere un breakpoint ad un'istruzione, posizionare il cursore sull'istruzione e usare il comando Set/Clear Breakpoint del menu Tools (oppure cliccare semplimente sul bordo sinistro accanto all'istruzione);
lanciare il metodo main eseguendo le istruzioni passo/passo (utilizzare i pulsanti Step Step Into della finestra del debugger).

Si noti, in particolare, come ciascuna attivazione di fibonacci rimanga sospeso nel punto in cui ha effettuato una delle due attivazioni ricorsive, e come dopo il ritorno dalla prima attivazione ricorsiva venga eseguita la seconda attivazione ricorsiva.

Esercizio 10B

Si consideri un'area paludosa costituita da R×C zone quadrate, con R e C noti, ognuna delle quali può essere una zona di terraferma (transitabile) o una zona di sabbia mobile (non transitabile). Ogni zona della palude è identificata da una coppia di coordinate < r, c >, con 0 < = r < R e 0 < = c < C. Diremo che r rappresenta la riga e c la colonna della zona < r, c >. Per passaggio si intende una sequenza di zone di terraferma adiacenti che attraversano la palude da sinistra (colonna pari a 0) a destra (colonna pari ad C - 1). Siamo interessati ai passaggi in cui ad ogni passo ci si muove verso destra, per cui da una zona in colonna c si va ad una zona in colonna c + 1. In altre parole, la zona in posizione < r, c > si considera adiacente alle zone in posizione < r - 1, c + 1 >, < r, c + 1 > e < r + 1, c + 1 >, come mostrato nella seguente figura.

Nella figura che segue, il carattere '*' rappresenta una zona di terraferma mentre il carattere 'o' rappresenta una zona di sabbia mobile. La palude 1 è senza passaggi, mentre la palude 2 ha un passaggio (evidenziato, usando '#' al posto di '*').

Per rappresentare una palude, si utilizzi la classe Palude già realizzata (file Palude.java) che esporta i seguenti metodi:

Palude(int righe, int colonne, double probTerra)
costruttore che costruisce una palude casuale, dati il numero di righe e di colonne, ed un valore reale compreso tra 0 e 1 che rappresenta la probabilità che una generica zona sia di terraferma;
int getNumRighe()
restituisce il numero di righe;
int getNumColonne()
restituisce il numero di colonne;
boolean terra(int r, int c)
verifica se la zona di coordinate < r, c > è di terra.
String toString()
metodo che effettua overriding del metodo toString di Object, in modo da stampare una palude, usando il carattere '*' per una zona di terraferma, ed il carattere 'o' per una zona di sabbia mobile.

Si richiede di verificare l'esistenza di almeno un passaggio e stamparlo se esiste (se ne esiste più di uno è sufficiente stampare il primo trovato). In particolare, si richiede di trovare una sequenza di zone della palude, in cui la prima posizione sia in colonna 1, mentre l'ultima sia in colonna C. Ogni posizione della sequenza deve essere adiacente alla successiva. Per esempio, se la prima posizione è < 3, 1 >, la seconda può essere < 4, 2 >, ma non < 3, 3 >. Dal momento che ad agni passo dobbiamo muoverci verso destra, il percorso sarà lungo esattamente C passi.

Per rappresentare un cammino, facciamo notare che esso deve avere lunghezza C, ovvero pari al numero di colonne della palude, e che le zone attraversate dal cammino stanno su righe successive a partire da 0 fino ad arrivare ad C - 1. Quindi, possiamo usare un array di C elementi interi, nel quale il valore del generico elemento di indice c è pari all'indice r di riga della posizione < r, c > attraversata dal cammino. Ad esempio il cammino evidenziato nella palude 2 di sopra è rappresentato dall'array {1,2,3,3,3,2}.

Si realizzi una classe cliente della classe Palude che contiene i seguenti metodi statici:

static boolean cercaCammino(Palude p, int r, int c, int[] camm)
metodo privato ausiliario che, presi in ingresso una palude p e le coordinate r e c di una zona, determini se esiste nella palude un cammino dalla zona <r,c> al bordo destro; se tale cammino esiste, l'array camm passato come parametro deve essere aggiornato in modo che le componenti da quella di indice c in poi contengano le posizioni del cammino trovato.
static boolean attraversaPalude(Palude p, int[] camm)
metodo privato ausiliario che, presi in ingresso una palude p ed un array camm (che si può supporre già creato, ma i cui valori non sono ancora inizializzati), verifica l'esistenza di un cammino che attraversa la palude a partire da tutte le posizioni della prima colonna; se esiste un cammino, l'array camm dovrà contenere la rappresentazione di tale cammino, come descritto sopra.
static String stringaCammino(Palude p, int[] camm)
metodo pubblico che, presi in ingresso una palude p ed un array camm che rappresenta un cammino, restituisce una stringa che rappresenta la palude p in cui il cammino camm è evidenziato usando il carattere '#'.
static void main(String[] args)
metodo pubblico che:
1. legge da tastiera il numero di righe e di colonne di una palude e la probabilità di terra in una zona (reale tra 0 e 1);
2. crea in modo casuale una palude con il numero di righe e colonne e la probabilità di terra specificati;
3. crea l'array che dovrà contenere l'eventuale cammino trovato;
4. determina se esiste un cammino che attraversa la palude invocando il metodo attraversaPalude e, se esiste, lo stampa usando stringaCammino.

Soluzione