Según la leyenda, los monjes de un templo tenían que mover una pila de 64 discos sagrados de un sitio a otro. Sólo podían mover un disco al día y, en el templo, sólo había otro sitio en el que podían dejarlos, siempre ordenados de forma que los mayores quedasen en la base. El día en que los monjes realizasen el último movimiento,el final del mundo habría llegado… ¿en cuántos días?

Me recuerda bastante a las torres de Hanoi, el algoritmo con el que todos nos hemos topado durante nuestras clases de programación o informática, el juego es bastante sencillo, consiste en tres varillas verticales y n número de discos, los discos se colocan de mayor a menor en la primer varilla de manera ascendente y no se puede colocar un disco más grande sobre uno de menor tamaño, el objetivo del juego consiste en pasar todos los discos a la tercer varilla colocados de mayor a menor ascendentemente, es decir que el disco más grande debe estar hasta abajo y el más pequeño arriba, cuanto más discos se involucran mayor cantidad de movimientos se requieren, para cuando se tienen 3 discos se realizan 7 movimientos, con 4 discos 15 movimientos, etc., esto sugiere que la fórmula para hallar la cantidad de movimientos necesarios para mover n discos es 2n-1 así que por ejemplo para 64 discos queda así: 264-1.

Suponiendo que los monjes son muy veloces, y que pueden realizar un movimiento por segundo, les tomaría como 18,446,744,073,709,551,615 segundos, que equivale a 307445734561825860.25 minutos, es decir a 5124095576030431.0041666666666667 horas, que a su vez equivale a 213503982334601.29184027777777778 días, y que a su vez equivale a 584942417355.07203243911719939117 años (suponiendo que no existen años bisiestos) en letras: Quinientos ochenta y cuatro mil novecientos cuarenta y dos millones cuatrocientos diecisiete mil trescientos cincuenta y cinco años, ni siquiera el universo es tan antiguo así que si algún día el mundo se fuera a acabar pues aun falta mucho, y ya que estaba hablando de clases de programación, pues manos a la obra, el pseudocódigo quedaría así(aplicando recursividad):


inicio
entero cantidad_de_discos
caracter comienzo='A', auxiliar='B', final='C'
leer cantidad_de_discos
hanoi(cantidad_de_discos, comienzo, auxiliar, final)
fin

inicio hanoi(int Discos, int Com, int Aux, int Fin)
si (Discos = 1) entonces
imprimir Com "->" Fin
si_no
hanoi(Discos -1, Com, Aux, Fin)
imprimir Com "->" Fin
hanoi(Discos-1, Aux, Com, Fin)
fin_si
fin

Y traducido a lenguaje de programación C queda así:


#include "stdio.h"
#include "stdlib.h"

void hanoi
(int discos,int comienzo, int auxiliar, int final);

int main(void){
system("clear");
char comienzo='A';
char auxiliar='B';
char final='C';
int cantidad_de_discos;
printf("Cantidad de discos: ");
scanf("%d",&cantidad_de_discos);
fflush(stdin);
hanoi(cantidad_de_discos,comienzo,auxiliar,final);
printf("\n");
return 0;
}

void hanoi
(int _cant,int _com, int _aux, int _fin){
if(_cant==1){
printf("%c->%c",_com,_fin);
}
else{
hanoi(_cant-1,_com,_fin,_aux);
printf("\n%c->%c\n",_com,_fin);
hanoi(_cant-1,_aux,_com,_fin);
}
}

Si eres muy curioso y deseas compilar este código, hazlo en gcc, de esta manera:

gcc hanoi.c -o hanoi  && ./hanoi

Y sí además quieres ayudar a los monjes a calcular el año del fin del mundo, ingresa 64 como valor del número de discos, y cuando tengas la fecha del fin del mundo, escribela aquí como comentario 😉
😀

Anuncios