|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 |
/* 5x07-Torres_de_Hanoi_parte_2 24/01/2012 Escribe un programa (se recomienda que sea recursivo) que dé solución al problema de las torres de Hanoi. El enunciado es el siguiente: Se dispone de una torre formada por varios discos de diferentes diámetros denominada torre O (origen), donde cada disco es de diámetro inferior a todos los que están por debajo. Se dispone de otras dos torres para dejar discos, una denominada torre A (auxiliar) y otra torre D (destino). El problema consiste en pasar todos los discos de la torre O a la torre D respetando dos normas muy simples: Los discos se pasan de una torre a otra de uno en uno. Nunca un disco de mayor diámetro puede estar sobre otro de menor diámetro. Se preguntará al inicio del programa por el tamaño de la torre O (entendiendo que tendrá el número de discos indicados, con algún límite preestablecido). Las torres A y D estarán inicialmente vacías. Se debe ofrecer la solución que da el programa a este problema paso a paso, mostrando el resultado de una forma gráfica. El inicio podría ser algo así: * *** ***** ******* ********* =========== ========== ========== O A D */ /* Formula para calcular movimientos mínimos necesarios: m = 2^n -1 http://www.rodoval.com/heureka/hanoi/ */ #include <stdio.h> #include <stdlib.h> void imprime( int *tab, int fil, int col, int ultNum ) { /* Precondición: *tab Puntero a una matriz de tipo entero. fil Entero que indica el numero de filas de la matriz. col Entero que indica el numero de columnas de la matriz. disc Parámetro de tipo entero que indica el numero de discos usados. ultNum Entero que indica el numero que esta usando el disco mas grande. */ int f, c; int i, esp; for( c=col-1; c >= 0; c-- ) { for( f=0; f < fil; f++ ) { esp = ( ultNum - tab[col*f+c] )/2; // Espacios a la izquierda for( i=0; i < esp; i++ ) printf( " " ); // Imprime los comodines for( i=0; i < tab[col*f+c]; i++ ) printf( "*" ); // Espacios a la derecha for( i=0; i < esp; i++ ) printf( " " ); printf( "\t" ); }; printf( "\n" ); }; }; void mueveDisco( int *tab, int fil, int col, int ultNum, int filOrig, int filDest ) { /* Precondición: *tab Puntero a una matriz de tipo entero. fil Entero que indica el numero de filas de la matriz. col Entero que indica el numero de columnas de la matriz. disc Parámetro de tipo entero que indica el numero de discos usados. ultNum Entero que indica el numero que esta usando el disco mas grande. filOrig Entero que indica el numero de fila de la matriz en la cual hay que coger el numero/disco filDest Entero que indica el numero de fila de la matriz en la cual hay que dejar el numero/disco. Poscondición: Se mueve el disco y se llama a la función que imprime el tablero. */ int cO=col-1, cD=col-1; // Se busca el disco que se encuentre mas arriba y por lo tanto el mas pequeño de la fila de origen. while( cO >= 0 && tab[col*filOrig+cO] == 0 ) { cO--; }; if( cO < 0 ) cO = 0; // Ahora se calcula cual es la posición libre mas arriba de la fila de destino while( cD >= 0 && tab[col*filDest+cD] == 0 ) { cD--; }; // Se mueve el disco de la fila de origen a la de destino: tab[col*filDest+cD+1] = tab[col*filOrig+cO]; tab[col*filOrig+cO] = 0; // Se imprime el tablero: imprime( tab, fil, col, ultNum ); }; void hanoi( int *tab, int fil, int col, int disc, int ultNum, int O, int A, int D ) { /* Precondición: *tab Puntero a una matriz de tipo entero. fil Entero que indica el numero de filas de la matriz. col Entero que indica el numero de columnas de la matriz. disc Parámetro de tipo entero que indica el numero de discos usados. ultNum Entero que indica el numero que esta usando el disco mas grande. O,A,D Tres enteros que indican la fila desde donde se ha de coger el disco y a donde se ha de traspasar. La primera vez que se llama a hanoi tienen los valores de: 0 ,1 y 2 respectivamente. Poscondición: Se llama recursivamente a hanoi hasta resolver el tablero. */ if( disc==1 ) { // Se borra la pantalla, se imprime la tabla y se hace una pausa que varia dependiendo del numero de discos: system("clear"); mueveDisco( tab, fil, col, ultNum, O, D ); if(col<=5) system("sleep 0.8"); else if(col<=10) system("sleep 0.3"); else if(col<=15) system("sleep 0.06"); else if(col>15) system("sleep 0.02"); } else { hanoi( tab, fil, col, disc-1, ultNum, O, D, A ); system("clear"); mueveDisco( tab, fil, col, ultNum, O, D ); if(col<=5) system("sleep 0.8"); else if(col<=10) system("sleep 0.3"); else if(col<=15) system("sleep 0.06"); else if(col>15) system("sleep 0.02"); hanoi( tab, fil, col, disc-1, ultNum, A, O, D ); }; }; main() { int fil=3, col, *tablero = NULL; int f, c, disc=1, ultNum; printf( "Indique el numero de discos: " ); scanf( "%i", &col ); tablero = (int *)malloc( sizeof(int)*fil*col ); // Resetea las torres poniendo "los discos" en una de ellas y 0 en el resto. for( f=0; f < fil; f++ ) for( c=col-1; c >= 0; c-- ) if( f==0 ) { tablero[col*f+c] = disc; disc+=2; } else tablero[col*f+c] = 0; ultNum = disc; // Se imprime el tablero antes de iniciar ningún movimiento: system("clear"); imprime( tablero, fil, col, ultNum ); system("sleep 1"); // Se llama a hanoi para comenzar "la partida": hanoi( tablero, fil, col, col, ultNum, 0, 1, 2 ); }; |
Gracias!!! Gracias!!! Gracias!!! Gracias!!! Gracias!!! Gracias!!! 1000 Gracias!!!
No hay de que, también lo tienes en java xD
una pregunta !! no sabes donde puedo encontrar el algoritmo de Torres de Hanoi pero interactiva??que no sea recursivo la solucion!!! porque para mi trabajo me piden de las dos formas !!!
Prueba con alguno de estos códigos:
http://www.elrincondelc.com/nuevorincon/foros/viewtopic.php?p=60099&sid=c8aae842e60c03446aa570a6840907b1
Muchas Gracias !!! si me sirvió!!!
Una ultima consulta!!! conoces alguna pagina donde pueda encontrar el algoritmo de MERGE SORT?? es un algoritmo de ordenamiento basado en la teoria divide y vencerás si sabes de alguna pagina me ayudarias muchisimo gracias!!!
Ese algoritmo no me suena, conocía el de la burbuja pero ese no.
Prueba a ver con esto:
Saludos.
Hola, muchas gracias por publicar este programa, mas yo tengo un problema y espero me puedas ayudar, sucede que al compilar me sale un error donde dice no se puede iniciar el programa e indica la dirección donde se guardó y por ultimo dice el sistema no pudo encontrar el archivo especifico
Hola,
El programa no tiene nada raro salvo los system() que solo te irán si usas linux, si no borrarlos o sustitúyelos por unos cuantos printf(«\n») para simular el limpiado de pantalla.
A parte de eso el resto de codigo es normal, si no te compila prueba a a ver si un «hola mundo» te funciona… podría ser problema de tu IDE.
Saludos.
tambien dice esto; Excepción no controlada del tipo ‘System.NullReferenceException’ en tp1.exe
Información adicional: Referencia a objeto no establecida como instancia de un objeto, espero me puedas ayudar y gracias de igual modo por tu atencion
Esta muy bien tu programa!!! Muchas gracias por compartir tu trabajo y asi ayudarnos!!
graciassssss………no se si me puedes ayudar necesito q ademas vaya mostrando a que columna se mueve por ejemplo O => A
Hola,
Este ejemplo es solo gráfico, si quieres saber las posiciones échale un vistazo a este código:
https://giltesa.com/2012/01/24/5×06-torres-de-hanoi-parte1/
Saludos.
Hola, soy principiante en C ya que justo acabo de empezar a estudiar este año y no entiendo lo de system(sleep) hay alguna otra instrucción por la que se pueda sustituir para que pueda entenderlo mejor?
Gracias de antemano por tu gran trabajo 😀
Aquí tienes información:
http://www.tutorialspoint.com/c_standard_library/c_function_system.htm
http://www.programmingsimplified.com/c/dos.h/delay
Saludos.
Hola buenas, me podrías explicar que hace el puntero *tablero?
No logro entender lo que hace :S
Gracias!
Hola,
Es un array de números enteros declarado en tiempo de ejecución para así poder reservar la memoria necesaria para almacenar el estado de las tres torres.
Las torres se representan en el array de forma horizontal, por ello el array tiene 3 filas y n columnas.
Te recomiendo que debugees el código con Eclipse y entenderás mejor qué hace.
Saludos.
gracias loko un 10 en prog tk <3