Un Simpatico Algoritmo!, la torre di Hanoi Opzioni

[pottydj]

Esercizio: Torre di Hanoi
Siano dati 3 pioli verticali, numerari da 0 a 2, ed un numero n di dischi di dimensioni decrescenti.
All’inizio del gioco i dischi sono tutti impilati in ordine di grandezza decrescente, dal basso verso l’alto, sul
primo piolo.
L’obiettivo del gioco è quello di spostare tutti i dischi dal piolo 0 al piolo 1 rispettando le seguenti regole:
1. è possibile spostare un solo disco alla volta
2. un disco non può essere impilato su un altro disco di dimensioni più piccole
NOTA: Il piolo 2 è usato come piolo di supporto durante i trasferimenti.

Il seguente algoritmo risolve il problema osservando che, l’unico modo per spostare il disco più grande dal
piolo 0 al piolo 1 consiste nello spostare prima tutti gli altri dischi sul piolo 2. Quindi:
1. sposta i primi n − 1 dischi dal piolo 0 al piolo 2, rispettando la legge
2. sposta l’ultimo disco dal piolo 0 al piolo 1
3. sposta i primi n − 1 dischi dal piolo 2 al piolo 1
I punti 1 e 3 implicano la risoluzione del problema di dimensione n − 1 con una permutazione dei nomi dei
pioli (al secondo passo il piolo 0 diviene il piolo di supporto).

CODICE

//Utilizzando il tipo di dato pila per definire un piolo, la procedura specifica in precedenza per la risoluzione del problema può essere così codificata:

void torredihanoi ( int n, piolo origine, piolo destinazione, piolo intermedio ) {
if ( n == 1 ) {
muovidisco ( origine , destinazione );
} else {
torredihanoi ( n − 1 , origine , intermedio , destinazione ); //RICORSIONE!!
muovidisco ( origine , destinazione );
torredihanoi ( n − 1 , intermedio , destinazione , origine ); //RICORSIONE!!
}
}


La procedure muovidisco deve:
1. leggere l’elemento di testa dal piolo origine (LEGGIPILA) e scriverlo in testa al piolo destinazione
(SCRIVIPILA)
2. cancellare l’elemento di testa del piolo origine (CANCPILA)

in pratica questo algoritmo varia esponenzialmente! Se si usano anche solo 18 dischi di dimensione crescente (che poi nell'impelementazione sono semplicemente dei valori interi crescenti) il tempo di calcolo (costo computazionale) equivale ad 1 giorno!! con 31-32 si passa già ad un secolo... affascinante!! Che ne dite?!

[potemkin]

x me è stupendo!!!

[cj@cc.gatech.edu]

E' il cosiddetto gioco delle Torri di Hanoi (va riempito il piolo 2).
E' uno dei primissimi algoritmi che trovi in tutti i libri sull'argomento.

C'è anche una leggenda in merito, che dice che dei sacerdoti devono risolverne uno con 64 dischi e che quando avranno terminato il mondo terminerà (18.446.744.073.551.615 mosse)

[galva]

pot quando lo facciamo ?

(sempre che tu non l'abbia già fatto !)

[MJ83®]

Ce l'avevo sul vecchio cellulare sto giochino, mi sembra che ci fossero 7-8 dischi e il mio record era di circa 20-30 secondi, non ricordo con esattezza (IMG:http://www.ferraraforum.it/style_emoticons/default/icon_wink.gif)

Messaggio modificato da MJ83® il 26 Jan 2006 - 19:17

[cj@cc.gatech.edu]

C'era anche in Ultima VIII... chi di voi l'ha finito... c'è passato :\

[pottydj]

(sempre che tu non l'abbia già fatto !)

no, non l'ho ancora fatto, l'ho solo riguardato (IMG:http://www.ferraraforum.it/style_emoticons/default/4.gif)

direi che nel weekend dovremmo risolverlo..

[pottydj]

CE L'HO FATTA AD IMPLEMENTARLO! (IMG:http://www.ferraraforum.it/style_emoticons/default/bbcmoi.gif)
vabeh nn era poi difficile (IMG:http://www.ferraraforum.it/style_emoticons/default/4.gif)

CODICE

#include "pile.h"

typedef pila piolo;
int ndischi=21;

void muovidisco(piolo origine, piolo destinazione);
void torredihanoi(int ndischi, piolo origine, piolo destinazione, piolo intermedio);

void muovidisco(piolo origine, piolo destinazione){
     tipoelem temp;
     temp=leggipila(origine);
     inpila(temp,destinazione);
     fuoripila(origine);
     }

void torredihanoi(int ndischi, piolo origine, piolo destinazione, piolo intermedio){
     if (ndischi==1) muovidisco(origine, destinazione);
     else{
          torredihanoi(ndischi-1,origine,intermedio,destinazione);
          muovidisco(origine,destinazione);
          torredihanoi(ndischi-1,intermedio,destinazione,origine);
          }
     }

int main()
{
  int i;                                 //numero dischi
  piolo origine,intermedio,destinazione;
  origine=creapila();
  intermedio=creapila();
  destinazione=creapila();
  for(i=ndischi;i>0;i--)inpila(i,origine);         //inizializzo il piolo con dischi di diametro decrescente dal basso
  printf("elem in cima al piolo origine : %d \n",leggipila(origine));         //stampo l'elem in cima alla pila dopo l'inizializzazione (1, il disco dal diametro + basso)
  torredihanoi(ndischi,origine,destinazione,intermedio);
  printf("elem in cima al piolo destinazione : %d \n",leggipila(destinazione));

  getchar();
  getchar();

  return 0;
}

ecco anche le funzioni leggipila() e fuoripila(), con le relative leggilista() e uorilista()

CODICE

typedef struct cella * lista;
typedef struct cella * posizione;
typedef int tipoelem;
typedef lista pila;

struct cella{
    lista precedente;
    tipoelem valore;
    lista successivo;
    };

tipoelem leggipila(pila P) {
    return (leggilista(ultimolista(P)));
    }

void fuoripila(pila P) {
    posizione pos = ultimolista(P);
    canclista(&pos);
    }

tipoelem leggilista(posizione P) {
    return P->valore;
    }

lista ultimolista(lista L) {
    return L->precedente;
    }

void canclista(posizione * P) {
    posizione temp;
    temp = *P;
    
    ((*P)->precedente)->successivo = (*P)->successivo;

    ((*P)->successivo)->precedente = (*P)->precedente;
    
    *P = (*P)->successivo;
    free (temp);
    }

[Senbee Norimaki]

Mi ricorda il famoso calcolo per cui, piegando un foglio di carta 64 volte, si raggiunge uno spessore alto come la distanza fra la Terra e la Luna.

[MJ83®]

Solo in teoria però, perché è provato che è impossibile piegare a metà per più di 7 volte un qualsiasi pezzo di carta (IMG:http://www.ferraraforum.it/style_emoticons/default/icon_mrgreen.gif)

[Senbee Norimaki]

Esatto. Vabbè, basta tagliarlo, invece di piegarlo. Però cavoli, ci vuole un pezzo bello grosso!

[Frabe]

tipo la scacchiera e i chicchi di grano?

[pottydj]

Esatto. Vabbè, basta tagliarlo, invece di piegarlo. Però cavoli, ci vuole un pezzo bello grosso!

uhmm probabilmente per quanto grosso sia se lo dividi sempre a metà diventa comunque piccolo perchè la parte che togli è proporzionalmente grande tanto + è grande quella iniziale..

uhmm boh.. D

[bzbiz]

Up

[Galen]

Ah, da piccolo ce l'avevo come rompicapo, ho ancora la scatoletta di legno con i pioli e i dischi. Se sapevo che c'era un algoritmo... (IMG:style_emoticons/default/sarcastica.gif)

[Matt]

algoritmi........... (IMG:style_emoticons/default/icon_rolleyes.gif)
fabio schifano.... (IMG:style_emoticons/default/icon_rolleyes.gif)

[tasso85]

Schifano NUOOOOOOOOO!

(IMG:style_emoticons/default/4.gif)

comunque, quell'algoritmo funzionerà anche, ma se eliminate la ricorsione va MOLTO più veloce...

[sayian]

Nella mia breve esperienza di ottimizzazione di algoritmi, di solito ho constatato che le versioni iterative sono sensibilmente più lente e meno efficiente rispetto a quelle ricorsive. Che io sappia, l'unico handicap degli algoritmi ricorsivi è il limite di memoria dello stack.

[A.L.G.]

non ho capito una fava... algoritmo?

[tasso85]

Nella mia breve esperienza di ottimizzazione di algoritmi, di solito ho constatato che le versioni iterative sono sensibilmente più lente e meno efficiente rispetto a quelle ricorsive. Che io sappia, l'unico handicap degli algoritmi ricorsivi è il limite di memoria dello stack.

eh no eh! aggiungi tutto il lavoro per creare i vari recordi di attivazione, allocare la memoria, ecc ecc... quello che ottieni è che l'algoritmo ricorsivo è generalmente più lento ma MOLTO più facile da scrivere

io avevo provato con un semplice algortimo per la serie di Fibonacci.. ricorsivo, era lentino, già a valori non enormi ci metteva parecchio... iterativo, una scheggia

[sayian]

Corretto, ho sbagliato io, mi ricordavo male. (IMG:style_emoticons/default/sisi.gif)