El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
- Sólo se puede mover un disco cada vez.
- Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
- Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
[fuente Wikipedia]
A continuación presento una implementación de este juego en C++, usando la estructura pila.
#include <iostream> #include <stack> using namespace std; void hanoi(int, stack<int>&, stack<int>&, stack<int>& ); int main(){ int n; stack<int> origen; stack<int> destino; stack<int> auxiliar; printf("Ingresa el número de discos:\n"); scanf("%d", &n);
//llenando la pila de origen con los discos for (int i=0; i<n; i++){ cout<<endl<<n-i<<endl; origen.push(n-i); } hanoi(n, origen, destino, auxiliar); } void hanoi(int n, stack<int> &origen, stack<int> &destino, stack<int>& auxiliar){ if (n == 1){ int top = origen.top(); destino.push(top); origen.pop(); return; } else{ //{mover n-1 discos de la torre origen a la torre auxiliar} hanoi(n-1, origen, auxiliar, destino); //{llamada recursiva} //Mover un disco de la torre origen a la torre destino int top = origen.top(); destino.push(top); origen.pop(); //{mover n-1 discos de la torre auxiliar a la torre destino} hanoi(n-1, auxiliar, destino, origen); //{llamada recursiva} } return; }
2 comments:
Interesante primo...
asi es :D
Post a Comment