[ansi c] torres de hanoi

[CrashNebula]

Estoy trabajando con las torres de hanoi. Quisiera que me ayudaran a descifrar
por qué mi código no funciona como debería.

El programa en debe ser gráfico y no narrativo. Algo como esto:
http://www.youtube.com/watch?v=xXTle8JYhys

Debo realizar el programa mediante funciones recursivas y no puedo utilizar métodos iterativos.

Las funciones donde probablemente esté el error son la g_MoverDiscos o g_TorreDeHanoiRecursiva.

En mi programa utilicé 3 arreglos unidimensionales para la "torres".
Uno que se llama Origen que se imprime a la izquierda, otro que se
llama intermedio que se imprime en el centro y el final se llama destino.





Mientras escribia esto note que los errores *parecen de impresión. :o. Creo que los
argumentos que se están pasando a la función imprimir se están cambiando debido a la
como tengo escrita la recursión en mi código. Alguna idea sobre como puedo solucionar
esto? (en caso de que esto sea el problema)

Cualquier ayuda es útil muchas gracias.

A continuación pondré las funciones donde creo que tengo el problema

Código C:

#define kMAX 30
void g_MoverDiscos(int liFilas,int liNDiscos,
 * * * * * * * * * int liTorreOrigen[kMAX],int liTorreDestino[kMAX])
{
 * *int liPosOrigen =0;
 * *int liPosDestino=liFilas-1;
 
 * *//Busqueda de la posicio del menor disco en el origen
 * *while(liTorreOrigen[liPosOrigen]==0 && liPosOrigen<liFilas-1)
 * *{
 * * * *liPosOrigen++;
 * *}
 
 * *//Busqueda de la posicion del tope de la torre destino
 * *while(liTorreDestino[liPosDestino]!=0 && liPosDestino>0)//Menor o igual
 * *{
 * * * *liPosDestino--;
 * *}
 * *liTorreDestino[liPosDestino]=liTorreOrigen[liPosOrigen];//Transferencia del disco
 * *liTorreOrigen[liPosOrigen]=0;//Al moverse el disco esta posicion se hace cero.
}
 
 
void g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX],
 * * * * * * * * * * * * * * int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
 
 * *if(liNDiscos==1)
 * *{
 
 * * * *g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
 * * * *system("cls");
 * * * *g_ImprimirDiscos(liFilas, liTorreOrigen,
 * * * * * * * * * * * * liTorreIntermedia, liTorreDestino);
 
 * *}//END if
 * *else
 * *{
 * * * *g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreOrigen,
 * * * * * * * * * * * * * * * *liTorreDestino,liTorreIntermedia);
 
 * * * *g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
 * * * *system("cls");
 * * * *g_ImprimirDiscos(liFilas, liTorreOrigen,
 * * * * * * * * * * * * *liTorreDestino,liTorreIntermedia);
 
 
 * * * *g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreIntermedia,
 * * * * * * * * * * * * * * * *liTorreOrigen,liTorreDestino);
 * *}//END else
}//END g_TorreDeHanoiRecursivo
 

///
/// Estas son las demás funciones de mi programa (todas estas están bien)
///

Código C:

/// Esta es para leer los discos
int giLeerDiscos(void)
{
 * *int liN;
 * *do
 * *{
 * * * *printf("\nIndique la cantidad de discos: ");
 * * * *scanf("%d",&liN);
 * * * *if(liN<1||liN>kMAX_DISCOS)
 * * * *{
 * * * * * *system("cls");
 * * * * * *printf("ERROR.OPCION NO ES VALIDA. VUELVA A INTENTAR\n\n");
 * * * *}
 * *}while(liN<1||liN>kMAX_DISCOS);
 * *return liN;
}
 
 
//Funcion incializa los arreglos a la condicion *que deben tener antes de jugar
void g_CondicionInicialHanoi(int liNDiscos,int liTorreOrigen[kMAX],
 * * * * * * * * * * * * * * int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
 * *int i;
 * *for (i=0;i<liNDiscos;i++)
 * *{
 * * * *liTorreOrigen[i]=i+1; * * * //Se colocan los discos desde el 1 en manera ascendente
 * * * *liTorreIntermedia[i]=0; * * //Se hace cero
 * * * *liTorreDestino[i]=0; * * * *//Se hace cero
 * *}
}
 
 
void g_ImprimirDiscos(int liFilas,int liTorreOrigen[kMAX],
 * * * * * * * * * * * *int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
 * *int i;
 
 * *for (i=0;i<liFilas;i++)
 * *{
 
 * * * *printf("%d\t",liTorreOrigen[i]);
 * * * *printf("%d\t",liTorreIntermedia[i]);
 * * * *printf("%d\t",liTorreDestino[i]);
 * * * *printf("\n");
 * *}
}
 
int *main()
{
 * *int liTorreOrigen[kMAX];
 * *int liTorreIntermedia[kMAX];
 * *int liTorreDestino[kMAX];
 * *int liNDiscos;
 * *int liFilas; // Es igual al numero inicial de discos. Define el espacio
 * * * * * * * * // de juego.
 
 
 * *liNDiscos=giLeerDiscos();
 * *liFilas=liNDiscos;
 * *//Condicion inicial del juego
 * *g_CondicionInicialHanoi(liNDiscos,liTorreOrigen,
 * * * * * * * * * * * * * *liTorreIntermedia,liTorreDestino);
 
 * *//Imprimir condicion inicial del juego
 * *system("cls");
 * *g_ImprimirDiscos(liNDiscos,liTorreOrigen,
 * * * * * * * * * * liTorreIntermedia,liTorreDestino);
 * *g_TorreDeHanoiRecursivo(liFilas, liNDiscos,liTorreOrigen,
 * * * * * * * * * * * * * *liTorreIntermedia,liTorreDestino);
 * *printf("\n");
return 0;
}
 

[CrashNebula]

Bump... Hay alguien ahí?

[vosk]

"...Hay alguien ahí?..."

Si que hay alguien, pero me parece que has colgado algo poco amigable visualmente (dicho de otra forma has colgado un toston que no se lo mira ni ...)

Lo unico que he visto es que usas system("cls") que no es estandar ('system' si, pero 'cls' no). A parte de eso: como se supone que alguien puede diferenciar los * con los que has rellenado el codigo de los desreferenciadores? Supongo que te tomaste la molestia de ponerlos por pares, por lo tanto el * impar indicará desreferencia. Si lo aplico a tu linea 48 me encuentro que:

Código:

int *main() {
    ...
    return 0;
}

Entras a la aplicacion con una funcion de tipo puntero a entero??

Siento no ser de mas ayuda.

Saludos
vosk

[amchacon]

Iniciado por vosk

Entras a la aplicacion con una funcion de tipo puntero a entero??

No seas irónico, sabes perfectamente que ha sido al copypastear el código

A ver, en situaciones como está conviene hacer una depuración más profunda del código... ¿Que es lo que pasa entre el paso 2 y 3?

[razpeitia]

Yo se regex.

Código C:

#define kMAX 30
void g_MoverDiscos(int liFilas,int liNDiscos, int liTorreOrigen[kMAX],int liTorreDestino[kMAX])
{
    int liPosOrigen =0;
    int liPosDestino=liFilas-1;
 
    //Busqueda de la posicio del menor disco en el origen
    while(liTorreOrigen[liPosOrigen]==0 && liPosOrigen<liFilas-1)
    {
        liPosOrigen++;
    }
 
    //Busqueda de la posicion del tope de la torre destino
    while(liTorreDestino[liPosDestino]!=0 && liPosDestino>0)//Menor o igual
    {
        liPosDestino--;
    }
    liTorreDestino[liPosDestino]=liTorreOrigen[liPosOrigen];//Transferencia del disco
    liTorreOrigen[liPosOrigen]=0;//Al moverse el disco esta posicion se hace cero.
}
 
 
void g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX], int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
 
    if(liNDiscos==1)
    {
 
    g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
    system("cls");
    g_ImprimirDiscos(liFilas, liTorreOrigen,
     liTorreIntermedia, liTorreDestino);
     
    }//END if
    else
    {
        g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreOrigen, liTorreDestino,liTorreIntermedia);
        g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
        system("cls");
        g_ImprimirDiscos(liFilas, liTorreOrigen, liTorreDestino,liTorreIntermedia);
 
        g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1, liTorreIntermedia, liTorreOrigen, liTorreDestino);
    }//END else
}//END g_TorreDeHanoiRecursivo
 
/// Esta es para leer los discos
int giLeerDiscos(void)
{
    int liN;
    do
    {
        printf("\nIndique la cantidad de discos: ");
        scanf("%d",&liN);
        if(liN<1||liN>kMAX_DISCOS)
        {
            system("cls");
            printf("ERROR.OPCION NO ES VALIDA. VUELVA A INTENTAR\n\n");
        }
    }while(liN<1||liN>kMAX_DISCOS);
    return liN;
}
 
 
//Funcion incializa los arreglos a la condicion *que deben tener antes de jugar
void g_CondicionInicialHanoi(int liNDiscos,int liTorreOrigen[kMAX], int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
    int i;
    for (i=0;i<liNDiscos;i++)
    {
        liTorreOrigen[i]=i+1; //Se colocan los discos desde el 1 en manera ascendente
        liTorreIntermedia[i]=0; //Se hace cero
        liTorreDestino[i]=0; //Se hace cero
    }
}
 
 
void g_ImprimirDiscos(int liFilas,int liTorreOrigen[kMAX], int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
    int i;
 
    for (i=0;i<liFilas;i++)
    {    
        printf("%d\t",liTorreOrigen[i]);
        printf("%d\t",liTorreIntermedia[i]);
        printf("%d\t",liTorreDestino[i]);
        printf("\n");
    }
}
 
int main()
{
    int liTorreOrigen[kMAX];
    int liTorreIntermedia[kMAX];
    int liTorreDestino[kMAX];
    int liNDiscos;
    int liFilas; // Es igual al numero inicial de discos. Define el espacio
     // de juego.
     
     
    liNDiscos=giLeerDiscos();
    liFilas=liNDiscos;
    //Condicion inicial del juego
    g_CondicionInicialHanoi(liNDiscos,liTorreOrigen, liTorreIntermedia,liTorreDestino);
     
    //Imprimir condicion inicial del juego
    system("cls");
    g_ImprimirDiscos(liNDiscos,liTorreOrigen, liTorreIntermedia,liTorreDestino);
    g_TorreDeHanoiRecursivo(liFilas, liNDiscos,liTorreOrigen,
    liTorreIntermedia,liTorreDestino);
    printf("\n");
    return 0;
}
 

[CrashNebula]

@Vosk: Como dijo amchacon fue al copiarlo que quedó así. Un error de novato posteando por primera vez en un foro de programación.Gracias de todos modos.

@razpeitia: Gracias por arreglar el código.

Si se fijan podran notar que la función en la linea 23 y la linea 37 tienen los últimos dos parametros intercambiados:

(linea 23) g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX], int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])

(linea 24) g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreOrigen, liTorreDestino,liTorreIntermedia);

(linea 42)g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1, liTorreIntermedia, liTorreOrigen, liTorreDestino);

@amchacon: Qué pasa entre el paso 2 y 3? No estoy completamente seguro así que voy a analizar.

En la funcion (linea 23) g_TorreDeHanoiRecursivo con liFilas=3, liNDiscos=3 la función se llama recursivamente tomando liNDiscos-1(linea 37) entonces el liNDiscos que se pasa será igual a 2. La funcion vuelve a llamarse para liNDiscos= 1 y se cumple la condición de la linea 26, se mueve un disco desde el origen hasta el destino y se imprime (paso 1) y termina esa función que fue llamada en la linea 37. En la linea 38 se hace un intercambio de disco y en la 40 se imprime nuevamente (paso2).

Al llamarse la función 2 veces. el orden de los parámetros no se vio afectado ya que si se intercambian las posiciones de dos elementos dos veces quedan en su estado original.
En la llamada de la linea 42 se cambian todos los parámetros de orden y la impresiones ya no quedan en el orden que le corresponde.

Creo que el problema son las impresiones y no la función recursiva porque la función imprime 7 veces y el resultado final está correcto. El numero mínimo de movimientos de la torre de hanoi se calcula como 2ˆn-1. Si n=3 entonces 2ˆn-1=7. Alguna idea de como indicarle a la función imprimir que el orden de los parámetros?

[CrashNebula]

Ya solucioné el problema. Mi solución no es elegante pero funciona.

La función:

Código C:

void g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX],
                             int liTorreIntermedia[kMAX],int liTorreDestino[kMAX])
{
.....
}
 

Le agregue tres argumentos los cuales se mantendrán en la misma posición dentro de la función.

Código C:

void g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX],
                             int liTorreIntermedia[kMAX],int liTorreDestino[kMAX],
                             int O[kMAX],int I[kMAX], int D[kMAX])
{
.....
}
 

Al ejecutarse el programa

Las posiciones de liTorreOrigen y O estarán ocupadas por el mismo arreglo
Las posiciones de liTorreIntermedia y I estarán ocupadas otro arreglo igual para las dos posiciones
Las posiciones de liTorreDestino y D es el mismo caso.

Todo el proceso recursivo estará a cargo de los parametros liTorreOrigen, liTorreIntermedia y liTorreDestino. Como O apuntará a la misma dirección de memoria que liTorreOrigen y así sucesivamente para los otros casos entonces puedo escribir

Código C:

g_ImprimirDiscos(liFilas,O,I,D);
 

y siempre se imprimirá en el orden correcto porque aprovecha que no se cambia de posición en la función y por ende apuntará correctamente a la dirección de memoria deseada.

Debajo posteare la nueva función:

Código C:

void g_TorreDeHanoiRecursivo(int liFilas, int liNDiscos,int liTorreOrigen[kMAX],
                             int liTorreIntermedia[kMAX],int liTorreDestino[kMAX],
                             int O[kMAX],int I[kMAX], int D[kMAX])
{
 
    if(liNDiscos==1)
    {
 
        g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
        system("cls");
        //g_ImprimirDiscos(liFilas,liTorreOrigen,liTorreIntermedia,liTorreDestino);
        g_ImprimirDiscos(liFilas,O, I, D);
        system("pause");
 
    }//END if
    else
    {
        g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreOrigen,
                                liTorreDestino,liTorreIntermedia,O,I,D);
 
        g_MoverDiscos(liFilas, liNDiscos, liTorreOrigen, liTorreDestino);
        system("cls");
         //g_ImprimirDiscos(liFilas,liTorreOrigen,liTorreIntermedia,liTorreDestino);
         g_ImprimirDiscos(liFilas,O,I,D);
 
         system("pause");
 
        g_TorreDeHanoiRecursivo(liFilas, liNDiscos-1,liTorreIntermedia,
                                liTorreOrigen,liTorreDestino,O,I,D);
    }//END else
}//END g_TorreDeHanoiRecursivo
 

vosk ahora escribí todo sin los desreferenciadores =P

Gracias por todo amigos.

[vosk]

Ves como al final todo se soluciona? Si ya se que no he aportada nada al tema, solo era cuestion de romper el hielo :)

Saludos
vosk