Le persone spesso mi danno il consiglio di "divide et impera", ma penso che per alcuni problemi non sia abbastanza. Il problema con un problema così complesso come il problema della Torre di Hanoi è che non è nemmeno possibile simulare o astrarre parti dei problemi, anche se li dividi in parti se sai cosa intendo. Quindi, qualcuno può darmi un approccio graduale nell'affrontare un problema così complesso e difficile?
Dividere e conquistare significa rendere il problema così piccolo da essere assolutamente banale da risolvere. Poi lo fai leggermente più grande e leggermente più grande, e cerca i modelli.
Per le Torri di Hanoi, qual è il problema più semplice? Un disco, spostato direttamente a destinazione. Il secondo più semplice è due dischi. Per prima cosa spostate un disco in un punto temporaneo, spostate il secondo nella destinazione, quindi spostate il primo disco nella destinazione.
La prossima iterazione è più difficile, ma il trucco qui è riconoscere che hai già dimostrato che puoi spostare una pila di due dischi, in modo da poterlo astrarre. Sposta una pila di due in una posizione temporanea, sposta il disco n th alla sua destinazione, quindi sposta la pila di due su di essa.
Ora inizi a vedere emergere un modello. Per i dischi n , per prima cosa spostate una pila di dischi n-1 , quindi il disco n th , quindi muovi la pila sopra di essa. Sai che è garantito che funzioni, perché puoi definire n-1 in termini di n-2 , che puoi definire in termini di n-3 , e così via fino ad arrivare a un disco, cosa banale.
Dove le persone si mettono nei guai sta cercando di mantenere ogni singola iterazione nella loro testa in una volta. Devi imparare a credere che funzioni per n-1 .
Ecco una completa implementazione funzionante in C. Passa in n come argomento.
#include <stdio.h>
#include <stdlib.h>
void hanoi(int n, const char* from, const char* to, const char* temp)
{
if (n == 1)
{
printf("Move disk 1 from %s to %s.\n", from, to);
}
else
{
// Move n-1 sized stack to temporary location
hanoi(n - 1, from, temp, to);
printf("Move disk %d from %s to %s.\n", n, from, to);
// Move n-1 sized stack from temp location to destination
hanoi(n - 1, temp, to, from);
}
}
int main(int argc, char* argv[])
{
if (argc < 2)
return -1;
int n = atoi(argv[1]);
hanoi(n, "left", "right", "middle");
return 0;
}
Leggi altre domande sui tag problem-solving