Newsgroup: it.comp.lang.javascript
Titolo: Qualcuno mi può spiegare la torre di Honoi?

Qualcuno mi può spiegare nei dettagli la torre di Honoi.
Grazie.
<h1>Torre di Hanoi</h1>
<p>Ecco le mosse per risolvere una torre di 5 dischi</p>
<script language="javascript">
var altezza = 5;
var dalpiolo = "a", alpiolo="c", conilpiolo="b";
hanoi(altezza,dalpiolo,alpiolo,conilpiolo);
 function hanoi(alt,dap,ap,cp){
  if(alt>=1){
   hanoi(alt-1,dap,cp,ap);
   muovidisco(dap,ap);
   hanoi(alt-1,cp,ap,dap);
   }
 }
 function muovidisco(da,a){
 document.write("Da "+da);
 document.write(" a "+a+" <br>");
 }
</script>

 Qualcuno mi può spiegare nei dettagli la torre di Honoi.
Quante pagine ho a disposizione? :-)
Le torri di Hanoi è il classico giochetto che serviva per illustrare la
ricorsività. Nato all'inizio del secolo scorso, fu ripescato, non a caso,
quando si è cominciato a diffondere il Pascal (che aveva fra i suoi punti di
forza proprio la ricorsività).
Si hanno un certo numero (N) di anelli, tutti di diametro diverso, infilati
in dei pioli. Regola fondamentale: l'anello più grande si deve trovare
sempre al di sotto di quelli più piccoli. Vi sono tre pioli (A, B e C).
All'inizio tutti gli anelli si trovano nel piolo A. Scopo del gioco è di
spostare tutti gli anelli dal piolo A al piolo C, usando il piolo B come
ausiliario, muovendone uno alla volta. Si può muovere solo l'anello che si
trova in cima alla pila degli anelli.
Per esempio, se abbiamo solo due anelli, la soluzione è semplice:
A->B
A->C
B->C
Nel caso di N anelli, la soluzione ricorsiva è questa:
1 - sposta N-1 anelli da A a B
2 - sposta l'anello rimasto da A a C
3 - sposta N-1 anelli da B a C
Le mosse 1 e 3 non sono vere e proprie mosse (solo 1 disco alla volta si può
muovere); costituiscono solo una semplificazione logica.
Per spostare la pila di N dischi costruiamo quindi la funzione che
rispecchia lo schema esposto:
function spostapila(N, sorg, dest, aux) {
    // sposta N-1 dischi da "sorg" a "aux", usando "dest" come ausiliario
    spostapila(N-1, sorg, aux, dest);
    // sposta l'anello rimasto da "sorg" a "dest"
    spostadisco(sorg, dest);
    // sposta N-1 dischi da "aux" a "dest", usando "sorg" come ausiliario
    spostapila(N-1, aux, dest, sorg);
}
Le tre istruzioni devono essere eseguite solo se N > 1 (altrimenti non si
uscirebbe più dalla funzione); per cui la funzione dovrebbe essere:
function spostapila(N, sorg, dest, aux) {
   if (N > 1) {
      spostapila(N-1, sorg, aux, dest);
      spostadisco(sorg, dest);
      spostapila(N-1, aux, dest, sorg);
  }
}
La funzione spostadisco deve soltanto stampare la mossa, ad esempio:
function spostadisco(sorg, dest) {
    document.write(sorg + " -> " + dest + "<br>");
}
Tutto qui...
Se la torre di hanoi è costituita da 5 dischi, dovrà essere richiamata con:
spostapila(5, "A", "C", "B");  // sposta 5 dischi da A a C usando B come
ausiliario.
Il numero minimo di mosse per spostare N dischi è 2^(N - 1) - 1
Nel tuo esempio vi è un errore:
    if (alt >= 1)
deve essere corretto in
    if (alt > 1)
Maurizio.

     if (alt >= 1)
Scusate, gli errori li ho fatti io, almeno due.
L'esempio andava benissimo. La mia funzione dovrebbe, invece, essere
corretta:
function spostapila(N, sorg, dest, aux) {
   if (N > 0) {
        ...
  }
}
Il secondo errore č che il numero minimo di mosse sono 2 ^ N - 1.
Maurizio.

 ha scritto nel messaggio
news:%nrD7.6702$7A4.4...@news.infostrada.it...


 Finché non mi saturi l'HD puoi andare avanti :)
Sei troppo buono :-)
Ora mi sento autorizzato a parlare delle "leggende" inventate attorno alle
torri di hanoi, dei monaci impegnati a spostare dischi trascinandoci verso
la fine del mondo, di versioni che funzionano in background (scambiano
dischi mentre l'utente sta leggendo un documento), di versioni che
funzionano anche con linguaggi non ricorsivi (ne esistono ancora?).
Ma forse anche la tua pazienza ha un limite.
Maurizio.