torres de hanoi

Preguntas RecientesCategoria: Otrotorres de hanoi
EstudiandoNoTanproparaprogramar preguntada 1 año antes

Como hacer el algoritmo de las torres de hanoi en c/c++ utilizando pilas? 
las reglas son :

  1. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.la
  2. Sólo puedes desplazar el disco que se encuentre arriba en cada varila
  3. solo se puede mover un disco a la vez

teniendo en cuenta que se tienen 3 torres(la de origen,destino,auxiliar), cualquier torre puede ser la de origen asi como la destino……por cada torre es una pila diferente 
el programa debe mostrar los movimientos hechos.

1 Respuestas
snow Staff contestada 1 año antes

La salida quedaria asi i=inicio u origen, a=auxiliar, d=destino
si el movimiento fue de auxiliar a destino se muestra a-d o si fue de inicio a destino i-d, etc…
se imprimen los movimientos a realizar separados por comas. si queres mas discos, solo aumentas los valores iniciales de las tres torres y cambias la variable numeroDiscos ademas de cambiar el if donde verifica la profundidad (profundidad == 9)

#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;
int numeroDiscos = 0;

bool llegoAlDestino(int torre[]) {
    int j = numeroDiscos;
    //printf("arreglo = %d ",numeroDiscos);
    for( int i = 0; i < numeroDiscos; i++) {
        //printf("%d = %d",torre[i], j);
        if(torre[i] != j) {
            return false;
        }
        j--;
    }
    return true;
}

void printMov(char mov[]) {
    //printf("%s",mov);
}

void printArreglo(int torre[]) {
    ///*
    int j = numeroDiscos;
    printf("[");
    for( int i = 0; i < numeroDiscos; i++) {
        printf("%d",torre[i]);
        j--;
    }
    printf("]");
    ///*/
}
bool hanoi (int profundidad,int inicio[], int indexI,int auxiliar[], int indexA, int destino[],int indexD,
    char camino[], int caminoSize) {
    //printArreglo(inicio);
    //printArreglo(auxiliar);
    //printArreglo(destino);
    //printf("p:%d,i:%d,a:%d,d:%d",profundidad,indexI,indexA,indexD);
    //printf("\n");

    if(llegoAlDestino(destino)) {
        printf("solucion:%s \n",camino);
        return true;
    }
    if(profundidad == 9) {

        //printf("----profundidad\n");
        //printf("%s",camino);
        return false;
    }
    profundidad++;
    if((indexI >=0 && indexD < 0) || (inicio[indexI] < destino[indexD] && indexI >= 0)) {
        //printf("i%d,a%d,d%d",indexI,indexA,indexD);
        strcat(camino,"i-d,");
        caminoSize = caminoSize + 4;
        printMov("ini a des,");
        indexD++;
        destino[indexD] = inicio[indexI];
        inicio[indexI] = 0;
        indexI--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {

            return true;
        }
        indexI++;
        inicio[indexI] = destino[indexD];
        destino[indexD] = 0;
        indexD--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    if((indexI >=0 && indexA < 0) || (inicio[indexI] < auxiliar[indexA] && indexI >= 0 )) {
        strcat(camino,"i-a,");
        caminoSize = caminoSize + 4;
        printMov("ini a aux,");
        indexA++;
        auxiliar[indexA] = inicio[indexI];
        inicio[indexI] = 0;
        indexI--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {

            return true;
        }
        indexI++;
        inicio[indexI] = auxiliar[indexA];
        auxiliar[indexA] = 0;
        indexA--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    if((indexA >= 0 && indexD < 0) || (auxiliar[indexA] < destino[indexD] && indexA >= 0)) {
        strcat(camino,"a-d,");
        caminoSize = caminoSize + 4;
        printMov("aux a des,");
        indexD++;
        destino[indexD] = auxiliar[indexA];
        auxiliar[indexA] = 0;
        indexA--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {
            return true;
        }
        indexA++;
        auxiliar[indexA] = destino[indexD];
        destino[indexD] = 0;
        indexD--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    if((indexA >=0 && indexI < 0) || (auxiliar[indexA] < inicio[indexI] && indexA >=0)) {
        //printf("especial i%d,a%d,d%d",indexI,indexA,indexD);
        strcat(camino,"a-i,");
        caminoSize = caminoSize + 4;
        printMov("aux a ini,");
        indexI++;
        inicio[indexI] = auxiliar[indexA];
        auxiliar[indexA] = 0;
        indexA--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {
            return true;
        }
        indexA++;
        auxiliar[indexA] = inicio[indexI];
        inicio[indexI] = 0;
        indexI--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    if((indexD >= 0 && indexI < 0) || (destino[indexD] < inicio[indexI] && indexD >= 0)) {
        strcat(camino,"d-i,");
        caminoSize = caminoSize + 4;
        printMov("des a ini,");
        indexI++;
        inicio[indexI] = destino[indexD];
        destino[indexD] = 0;
        indexD--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {
            return true;
        }
        indexD++;
        destino[indexD] = inicio[indexI];
        inicio[indexI] = 0;
        indexI--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    if((indexD >= 0 && indexA < 0) || (destino[indexD] < auxiliar[indexA] && indexD >= 0)) {
        strcat(camino,"d-a,");
        caminoSize = caminoSize + 4;
        printMov("des a aux,");
        indexA++;
        auxiliar[indexA] = destino[indexD];
        destino[indexD] = 0;
        indexD--;
        if(hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize)) {
            return true;
        }
        indexD++;
        destino[indexD] = auxiliar[indexA];
        auxiliar[indexA] = 0;
        indexA--;
        camino[caminoSize] = '\0';
        camino[caminoSize -1] = '\0';
        camino[caminoSize -2] = '\0';
        camino[caminoSize -3] = '\0';
        caminoSize = caminoSize - 4;
    }
    //printf("-----\n");
    return false;
}

int main()
{
    numeroDiscos = 3;
    int inicio[] = {3,2,1};
    int indexI = numeroDiscos - 1;
    int auxiliar[] = {0,0,0};
    int indexA = -1;
    int destino[]= {0,0,0};
    int indexD = -1;
    int profundidad = 0;
    char camino[900] = "";
    int caminoSize = -1;
    //printf(llegoAlDestino(destino)? "true":"false");
    hanoi(profundidad,inicio,indexI,auxiliar,indexA,destino,indexD,camino,caminoSize);

    return 0;
}

Your Answer

14 + 19 =