Corsi precedenti

Svolgimento guidato

Potenze

Il metodo

Per scrivere un metodo ricorsivo si può ragionare così. Vogliamo risolvere il problema su un input di taglia . Supponiamo di disporre di un “oracolo” che è in grado di risolvere tutte le istanze del problema di taglia minore di . Non ci interessa sapere come funziona questo “oracolo”: l’importante sapere che funziona. Invochiamo opportunamente l’oracolo, otteniamo dei risultati, e li combiniamo per risolvere il problema di taglia .

Per esempio nel caso del metodo potenza supponiamo di disporre di un oracolo che calcoli le potenze con esponente minore di ; in particolare l’oracolo calcola le potenze con esponente (si riveda come è definito nella pagina del problema). Consideriamo il caso di pari, dove . Per risolvere il problema è sufficiente invocare l’oracolo, che ci restituirà il valore di , e moltiplicare tale valore per se stesso per ottenere :

int k = n/2;
double p = oracoloPotenza(x, k);
return p * p;

Ora entra in gioco la ricorsione: l’oracolo da invocare non è altro che lo stesso metodo ricorsivo! Quindi il codice del caso pari diventa semplicemente:

int k = n/2;
double p = potenza(x, k);
return p * p;

Considerando tutti e tre i casi ( (caso base della ricorsione), dispari e pari) otteniamo il codice seguente:

public static double potenza(double x, int n) {
    if(n==0) return 1;
    else if(n%2 == 0) { //Se n è pari
      int k = n/2;
      double p = potenza(x, k);
      return p*p;
    } else { //n dispari
      int k = n/2;  //Quoziente della divisione di n per 2
      double p = potenza(x, k);
      return p*p*x;      
    }
  }

Analisi del costo

Ogni attivazione del metodo potenza ha, di per sé, costo costante (non ci sono cicli). Contiamo dunque quante volte il metodo viene attivato in conseguenza alla chiamata potenza(x, n), in funzione di n.

Osserviamo che nel corso di ogni chiamata in cui si ha un’attivazione ricorsiva del metodo, con input .
Quindi l’input delle varie attivazioni sarà rispettivamente (non superiore a) .

Ci fermeremo sicuramente quando l’input è diventato minore di 1 (perché allora sarà eseguito il caso base). Poiché nell’-esima attivazioni l’input vale non più di , si ha che per , ossia per . Ciò significa che dopo attivazioni si sarà raggiunto il caso base. Il costo è dunque .

Per finire, osserviamo che, essendo l’input un numero intero (), la dimensione di è data dal numero di bit richiesti per la rappresentazione (binaria) di . Indichiamo tale numero con : si ha che , ossia . Introducendo tale valore nel costo precedentemente determinato otteniamo il costo in funzione della dimensione dell’input: (costo lineare nel numero dei bit).

Permutazioni

E’ possibile usare la ricorsione nel seguente modo. Si consideri l’array di input arr come un insieme. Per risolvere il problema con dimensione n, fissiamo in tutti i modi possibili il primo elemento dell’array: una volta fissato il primo elemento, si trattera’ di permutare, in tutti i modi possibili, i restanti n-1 elementi. Abbiamo dunque un problema di dimensione n-1: siamo in grado di usare l’oracolo ricorsivo per trovare le permutazioni di tali elementi.

(da completare)

Labirinto

Suggerimenti per la risoluzione

Ricorsione

Si consiglia di risolvere il problema facendo uso della ricorsione. Infatti, osserviamo che esiste un percorso tra una stanza e la stanza se e soltanto se esiste un percorso tra una stanza adiacente ad e .

Dunque il metodo ricorsivo potrebbe effettuare le seguenti operazioni:

• verificare se coincide con (passo base della ricorsione: la destinazione è stata raggiunta). Se sì, restituire true.
• altrimenti:
  • per ciascuna cella adiacente a che sia una stanza e che non sia stata già visitata, cercare ricorsivamente se esiste un percorso da a . Se sì, restituire true.
  • infine, se abbiamo visitato tutte le stanze adiacenti senza successo, vuol dire che non esiste un percorso che porta a destinazione: restituire false.

Scrivere lo pseudocodice dell’algoritmo richiesto, e poi trasformarlo in codice Java. *Se si incontrano difficoltà*, continuare a leggere.

Rappresentazione dell’informazione

Rappresentazione del labirinto: il labirinto, evidentemente, può essere rappresentato usando una matrice di booleani (stanza/parete).

Marcatura delle stanze: tramite un’altra matrice di booleani si possono marcare le stanze visitate. Marcheremo una stanza all’inizio della visita di (ovvero dell’attivazione ricorsiva del risolutore a partire dalla stanza ). Osserviamo che, una volta che una stanza è stata marcata, è inutile (anzi, dannoso) esplorarla nuovamente: la marcatura non dovrà più essere rimossa.

Rappresentazione del percorso trovato: utilizzare una matrice di interi, inizializzata con zeri. Passare al metodo ricorsivo, come (ulteriore) parametro, la posizione della stanza visitata all’interno del percorso. Inizialmente tale posizione è 1; successivamente, se si sta visitando la stanza -esima del percorso, le visite ricorsive delle stanza adiacenti avranno come posizione . La posizione deve essere confermata (cioè scritta nella matrice) se e soltanto se la visita ha successo, cioè se e soltanto se l’attivazione attuale del metodo restituisce true.

Suggerimento S.O.S.: Pseudocodice

boolean risolviLabirintoRicorsivo(int i, int j, int id, int jd, int k) {
 
	if(!isStanza(i,j))  //Se non siamo su una stanza: es. parete o fuori dal labirinto
		return false;
 
	if(marca[i][j]) //Se la cella attuale è già marcata, non la visitiamo di nuovo
		return false;
 
	marca[i][j] = true;
 
	percorso[i][j]=k; //toglieremo questa marcatura se dovremo restituire false
 
	if(i==id && j==jd) //Caso base: destinazione raggiunta
		return true;
 
 
 
	//Per ogni cella adiacente: (iAd, jAd) in {(i, j-1), (i, j+1), (i-1, j), (i+1, j)}
	//invocare il metodo risolviLabirintoRicorsivo(iAd, jAd, id, jd, k+1).
	//Se questo restituisce true,
	//restituire true.
	[...]
 
 
	//Altrimenti:
	//non abbiamo trovato il percorso perché non esiste
 
	percorso[i][j]=0; //Togliamo la marcatura come parte del percorso
	return false;
 
}