Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 281 vistas

    Torre de Hanoi Algoritmo

    Cargado por

    eduardo
    El documento describe el rompecabezas clásico de las Torres de Hanói. Consiste en tres varillas y discos de diferentes tamaños apilados en una varilla inicial. El objetivo es transferir toda la pila a una varilla final siguiendo las reglas de que solo se puede mover un disco a la vez y los discos siempre deben apilarse de mayor a menor tamaño. La fórmula para calcular el número mínimo de movimientos necesarios es 2n - 1, donde n es el número de discos. Se explican soluciones recursivas y mediante estrategias

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Torre de Hanoi Algoritmo

    Cargado por

    eduardo
    281 vistas3 páginas
    El documento describe el rompecabezas clásico de las Torres de Hanói. Consiste en tres varillas y discos de diferentes tamaños apilados en una varilla inicial. El objetivo es transferir toda la pila a una varilla final siguiendo las reglas de que solo se puede mover un disco a la vez y los discos siempre deben apilarse de mayor a menor tamaño. La fórmula para calcular el número mínimo de movimientos necesarios es 2n - 1, donde n es el número de discos. Se explican soluciones recursivas y mediante estrategias

    Descripción original:

    algoritmo de torre de hanoi

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe el rompecabezas clásico de las Torres de Hanói. Consiste en tres varillas y discos de diferentes tamaños apilados en una varilla inicial. El objetivo es transferir toda la pila a una varilla final siguiendo las reglas de que solo se puede mover un disco a la vez y los discos siempre deben apilarse de mayor a menor tamaño. La fórmula para calcular el número mínimo de movimientos necesarios es 2n - 1, donde n es el número de discos. Se explican soluciones recursivas y mediante estrategias

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    281 vistas3 páginas

    Torre de Hanoi Algoritmo

    Cargado por

    eduardo
    El documento describe el rompecabezas clásico de las Torres de Hanói. Consiste en tres varillas y discos de diferentes tamaños apilados en una varilla inicial. El objetivo es transferir toda la pila a una varilla final siguiendo las reglas de que solo se puede mover un disco a la vez y los discos siempre deben apilarse de mayor a menor tamaño. La fórmula para calcular el número mínimo de movimientos necesarios es 2n - 1, donde n es el número de discos. Se explican soluciones recursivas y mediante estrategias

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 3

    LUIS EDUARDO FUNES GUTIERREZ

    201640274

    TORRE DE HANÓI

    Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el


    matemático francés Édouard Lucas. Este juego de mesa solitario consiste en un número de
    discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El
    objetivo del juego es crear la pila en otra de las estacas siguiendo ciertas reglas.

    El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de


    texto como introducción a la teoría de algoritmos.

    La fórmula para encontrar el número de movimientos necesarios para transferir n discos del poste
    A al poste C es: 2n - 1.

    Descripción
    El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas
    se apila un número indeterminado de discos (elaborados de madera) que determinará la
    complejidad de la solución, por regla general se consideran siete discos. Los discos se apilan
    sobre una varilla en tamaño decreciente de abajo a arriba. No hay dos discos iguales, y todos
    ellos están apilados de mayor a menor radio -de la base de la varilla hacia arriba- en una de las
    varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de
    la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar
    este objetivo, es necesario seguir tres simples reglas:

    1.Sólo se puede mover un disco a la vez.

    2. Un disco de mayor tamaño no se puede estar sobre uno más pequeño que él mismo.

    3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

    Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.

    Resolución
    La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de
    pasos para resolver el problema crece exponencialmente conforme aumenta el número de
    discos.

    Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos
    es impar la pieza inicial ira a destino y si es par a auxiliar.
    Solución simple
    Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en
    la varilla de origen.
    En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la
    varilla auxiliar.
    El disco n.°2 se debe mover, por regla, a la varilla destino.
    Luego, el disco n.°1 se mueve también a la varilla destino para que quede sobre el disco n.° 2.
    A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.°3, y se
    coloca en la varilla auxiliar.
    Finalmente, el disco n.°1 regresa de la varilla destino al origen (sin pasar por la auxiliar), y así
    sucesivamente.
    Es decir, el truco está en el disco más pequeño.

    Mediante recursividad

    Este problema se suele plantear a menudo en programación, especialmente para explicar la


    recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de
    discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos Hanói,
    con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

    Algoritmo Torres de Hanói (Complejidad Θ (2𝑛 ))

    Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada

    Salida: La pila destino

    1. sí origen == {1} entonces


    1. mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino)

    2. terminar

    2.si no

    1. Hanói ( {1, … , 𝑛 − 1},origen, destino, auxiliar) //mover todas las fichas menos la más
    grande (n) a la varilla auxiliar

    3. mover disco n a destino


    //mover la ficha grande hasta la varilla final

    4. hanoi (auxiliar, origen, destino)


    //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n)

    5. terminar
    Resolución Grafica:

    También podría gustarte