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?!

[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);
    }