Había una vez...
Algoritmos
En Delphi
| Volver | | Arbol | | Archivo | | Agenda | Base de Datos | | Básico |
| Editor | | Editor2 | | Fibonacci | | Hanoi | | Listas | | Matriz |
| Modelo 1 | | Modelo | | Polimorfismo | Punteros | | Sobrecarga | | Vectores |

Colega virtual, en esta page podrás observar una de las aplicaciones más tradicionales de la función recursiva, que te permite ahorrar muchas lineas de código repetitivo para lograr la misma acción.

En todos los lenguajes la recursividad permite a autoconvocarse a una función, todas las veces que sea necesario, hasta generar resultado esperado.

• .. unas torres, llamadas de Hanoi, o también Torres de Brama o el problema del fin del mundo,

  Esta historia se atribuye al matemático francés Édouard Lucasd'Amiens, que lo publicó en 1883 en París bajo el pseudónimo de "N. Claus de Siam".

• Se llamaron las Torres de Hanoi probablemente debido a que por esas fechas en las que Francia estaba involucrado militarmente en Tonkin y Annam el nombre Hanoi aparecía mucho en las primeras planas de los diarios.

• El problema está inspirado en una leyenda de un templo hindú en donde se empleaba un rompecabezas para probar la habilidad mental de los jóvenes sacerdotes.

• Otro matemático francés, De Parville, desarrolló en 1884 la siguiente historia, muy relacionada con el problema:

• "En el gran templo de Benarés, debajo de la cúpula que marca el centro del mundo, yace una base de bronce, en donde se encuentran acomodadas 3 agujas de diamante, cada una del grueso del cuerpo de una abeja y de una altura de 50 cm aproximadamente.

• En una de estas agujas, Dios, al momento de la creación, colocó 64 discos de oro -el mayor sobre el plato de bronce, y el resto de menor tamaño conforme se llega a la cima.

• Día y noche, incesantemente, los sacerdotes del templo mueven los discos de una agujaa otra de acuerdo con las leyes impuestas e inmutables de Brahma, que requieren que los sacerdotes se encuentren todo el tiempo laborando, no muevan más de un disco a la vez y que deben colocar el disco en alguna de las agujas de modo que no cubra a undisco de radio menor.

• Cuando los 64 discos hayan sido transferidos de la aguja en la que Dios colocó los discos, al momento de la creación, a otra aguja, el templo y los brahmanes se convertirán en polvo y junto con ellos el mundo desaparecerá." (De Parville, 1884).

El algoritmo que resuelve el problema de las torres de Hanoi es:

      
             Procedimiento Hanoi(n, i, j)
                     Si n=1 entonces
                        mover disco de i a j  
                     Si no entonces
                        Hanoi(n-1,i,6-i-j)
                        mover disco de i a j           
                        Hanoi(n-1,6-i-j,j)
                     Fin Si
             Fin Hanoi

• El caso trivial es una operación de coste constante (mover un disco). En el caso no trivial se realizan dos llamadas recursivas con tamaño de problema reducido por resta de 1 (mover n-1 discos) y una operación de coste constante (mover un disco).

• Luego se tiene recursividad de tipo Rec 1 con:a=2 (dos llamadas recursivas siempre)b=1 (se disminuye el tamaño de problema por resta de 1 disco)k=0 (operación trivial y adicional de coste constante)Aplicando la solución (Sol 1) se tiene:Es decir, se trata de un algoritmo de coste exponencial.

• Estos algoritmos son los llamados "intratables" debido a su elevado coste asintótico.

• Téngase en cuenta que si un monje moviera un disco por segundo para resolver el problema de las torres para 10 discos tardaría del orden de 210 segundos, es decir 1024 segundos o 17 minutos.

• Para 11 discos el tiempo se doblaría, es decir sería de unos 34 minutos. Para 20 discos el tiempo ya sería de unos 12 días.

• Para mover los 64 discos tardaría 264 segundos, es decir 1,84. 1019 segundos o sea algo así como ¡ 600.000 millones de años !.

• Si en lugar de realizar movimiento manual de discos, se simula en un computador rápido a razón de un movimiento por microsegundo la solución para 64 discos se alcanzaría en unos 600.000 años.

• O sea que el potente ordenador no evita que estemos todos calvos cuando se acabe de solucionar el problema (según la leyenda el mundo se acaba cuando los monjes hayan conseguido mover los 64 discos).

        //-------------------------------------------------
             //-PROCEDIMIENTO PARA CARGAR LA GRILLA
             
             void TForm1::MoverDisco(int desde,int hasta)
               {
                 grilla->Cells[0][0]="Desde el poste";
                 grilla->Cells[1][0]="Hasta el poste";
                 i++;
                 grilla->Cells[0][i]=desde;
                 grilla->Cells[1][i]=hasta;
               }             

              //--------------------------------------------------
              //-PROCEDIMIENTO PARA LA SOLUCION DE LAS TORRES
              
                void TForm1::MoverTorre(int disco,int uno,int dos,int tres)
                {
                 if (disco==1)
                  MoverDisco(uno,tres);
                 else
                  {
                   MoverTorre(disco-1,uno,tres,dos);
                   MoverDisco(uno,tres);
                   MoverTorre(disco-1,dos,uno,tres);
                  }
                }

             //-------------------------------------------------
             //--PROCEDIMIENTO PARA VER LA SOLUCION EN LA GRILLA
             
              void __fastcall TForm1::botonsolucionClick(TObject *Sender)
              {
               contegrilla->Visible=true;  
               MoverTorre(boxdiscos->Text.ToInt(),1,2,3);     
              }
             //-------------------------------------------------

  
         //------------------------------------------------
           procedure Tparcialhanoi.moverdisco(desde,hasta:integer);
              begin
               grilla.Cells[0,0]:='Desde el Poste';
               grilla.Cells[1,0]:='Hasta el Poste';
               i:=i+1;
               grilla.Cells[0,i]:=IntToStr(desde);
               grilla.Cells[1,i]:=IntToStr(hasta);
              end;

           //----------------------------------------------------
            procedure Tparcialhanoi.movertorre(disco,uno,dos,tres:integer);
             begin
              if(disco=1)then
               moverdisco(uno,tres)
              else
               begin
                 movertorre(disco-1,uno,tres,dos);
                 moverdisco(uno,tres);
                 movertorre(disco-1,dos,uno,tres);
               end;
             end;

            //------------------------------------------------
            procedure Tparcialhanoi.botonsolucionClick(Sender: TObject);
             begin
              contegrilla.Visible:=true;
              movertorre(StrToInt(boxdiscos.Text),1,2,3);
             end;
           //---------------------------------------------------
                             

José Gastón dice:

Las Torres de Hanoi son un problema matemático que ha divertido a muchos por mucho tiempo. Más que un problema, es realmente un juego.

Este juego que como dice la leyenda llevaría muchos años resolverlo, pero a través de la computación se puede resolver fácilmente. Se resuelve a través de una solución algoritmica que es recursiva.

Por ejemplo yo lo realicé pero en distintos lenguajes 'BUILDER C++' y 'DELPHI' que son muy buenos y que son del mismo padre 'BORLAND' pero con varias diferencias entre los dos que no son aceptables para mi, es el caso de la sintaxis de Builder que con su sensibilidad al tipo de letra tengo que estar alerta de una letra mayúscula o minúscula, y escribir las flechitas me cansa, pero esto es sólo una opinión en contra que BORLAND debería tener en cuenta y fuera de esto te digo que el lenguaje es muy bueno.

Así que si quieres convertirte en un monje y resolver la solución de las torres te recomiendo estos dos lenguajes.