Torre di Hanoi

La Torre di Hanoi (anche conosciuta come Torre di Lucas dal nome del suo inventore) è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti.

Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.

Il gioco fu inventato nel 1883 dal matematico francese Édouard Lucas che diffuse il gioco sotto lo pseudonimo di N. Claus de Siam, mandarino del collegio di Li-Sou-Stian. La leggenda secondo la quale in un tempio Indù alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d’oro secondo le regole della Torre di Hanoi (a volte chiamata Torre di Brahmā), è stata inventata dalla ditta che per prima ha messo in commercio il rompicapo. La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà. Esistono anche versioni videoludiche del rompicapo.

 

Eccovi il codice Java per la soluzione del problema della Torre di Hanoi (Complessità esponenziale):

 

public class TowersOfHanoi {

public void solve(int n, String start, String auxiliary, String end) {

if (n == 1) {

System.out.println(start + ” -> ” + end);

} else {

solve(n – 1, start, end, auxiliary);
System.out.println(start + ” -> ” + end);
solve(n – 1, auxiliary, start, end);

}

}

public static void main(String[] args) {

TowersOfHanoi towersOfHanoi = new TowersOfHanoi();
System.out.print(“Enter number of discs: “);
Scanner scanner = new Scanner(System.in);
int discs = scanner.nextInt();
towersOfHanoi.solve(discs, “A”, “B”, “C”);

}

}

 

Possiamo notare che la soluzione adottata è di tipo ricorsivo, cioè viene definita una funzione, solve(…), che per portare a termine il suo compito, richiama se stessa.

Il concetto è questo; prendiamo un problema A, lo scomponiamo in due sottoproblemi B e C più piccoli ma che hanno la stessa formulazione del problema originario A, e così via sino a che il problema si riduce in n problemi elementari dalla soluzione ovvia;

et voilà ! Il problema è risolto !

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *