Corsi precedenti

Prima Esercitazione in Laboratorio

In questa esercitazione si richiede di risolvere alcuni problemi tramite metodi ricorsivi.
In caso di difficoltà, è possibile consultare lo svolgimento guidato degli esercizi proposti.

Potenze

Per calcolare la potenza , con e , invece di eseguire moltiplicazioni è possibile sfruttare la seguente osservazione:

• se è pari, sia . Si ha: ;
• se è dispari, sia . Si ha: ;
• se , allora .

Si richiede di:

1. Scrivere un metodo double potenza(double x, int n) che restituisca il valore , facendo uso dell’osservazione precedente. Usare la ricorsione.
2. Effettuare opportuni test di funzionamento del metodo.
3. Determinare la complessità computazionale del metodo potenza in funzione:
   • di n;
   • della dimensione dell’input.

Permutazioni

Scrivere un metodo void permutazioni(int[] arr) che, ricevuto in input un array di interi distinti, stampi tutte le permutazioni dell’array.
Per esempio se arr = {1, 2, 3} un possibile output è il seguente:

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

Testare estensivamente il metodo, e determinarne la complessità computazionale.

Labirinti (esercizio da completare a casa)

Scrivere e testare una classe Java per la risoluzione di labirinti.

Un labirinto è una matrice le cui celle possono essere stanze (attraversabili) oppure pareti (non attraversabili). Ogni cella è identificata da una coppia di numeri naturali compresi fra e . Risolvere un labirinto tra la cella e la cella significa trovare un percorso che parta dalla cella , si muova per celle adiacenti (orizzontalmente o verticalmente) e libere (cioè stanze), e raggiunga la cella di destinazione .

La classe Labirinto deve contenere i seguenti metodi pubblici:

• Labirinto(int n): costruttore; n è la dimensione del labirinto. Inizialmente tutte le celle sono stanze.
• void impostaParete(int i, int j): fa sì che la cella (i, j) sia una parete.
• boolean risolviLabirinto(int is, int js, int id, int jd) cerca un percorso tra la cella (is, js) e la cella (id, jd). Restituisce true se e solo se un percorso siffatto esiste.
• int dammiPosizioneNelPercorso(int i, int j): se la cella (i, j) fa parte del percorso trovato dall’ultima invocazione del metodo risolviLabirinto, allora restituisce un intero che indica la posizione della stanza (i, j) all’interno del percorso trovato. La posizione è 1 per la stanza (is, ds), 2 per la stanza adiacente visitata immediatamente dopo, e così via. Se la cella (i, j) non fa parte del percorso, restituisce 0.

Effettuare test numerosi e frequenti. In particolare, scrivere un metodo main che crei il seguente labirinto (dove una cella grigia corrisponde ad una parete), lo risolva tra la cella (0, 0) e la cella (4, 4), e infine stampi il labirinto (in modo che sia facilmente intellegibile) con il percorso trovato.

Infine, calcolare la complessità computazionale del metodo risolviLabirinto in funzione della dimensione dell’input.

Commenti dei visitatori

Accedi per lasciare commenti.