Hanoi tornyai

Magyar

Kiejtés

• IPA: [ ˈhɒnojitorɲɒji]

Főnév

Hanoi tornyai

1. (matematika) A Hanoi tornyai egy klasszikus rekurzív probléma, amelyben adott:

• 3 oszlop ($A,B,C$), ahol az első oszlopon $n$ különböző méretű korong van, egymásra rakva, a legnagyobbtól a legkisebbig.
• A feladat az, hogy az összes korongot áthelyezzük az első oszlopból a harmadik oszlopba, a következő szabályok betartásával:

 # Egyszerre csak egy korongot mozgathatunk.
 # Egy nagyobb korong soha nem helyezhető egy kisebb korong tetejére.
 # Csak a legfelső korong mozgatható az oszlopokról.

Probléma Matematikai Modellje

A probléma rekurzív szerkezete:

• Ha $n=1$, a legkisebb korongot közvetlenül az induló oszlopból a céloszlopra helyezzük.
• Ha $n>1$:

 # Az $n-1$ korongot áthelyezzük a segédoszlopra.
 # Az $n$-edik (legnagyobb) korongot áthelyezzük az induló oszlopból a céloszlopra.
 # Az $n-1$ korongot áthelyezzük a segédoszlopról a céloszlopra.

A korongok mozgatásának minimális lépésszáma: $T(n)=2^{n}-1$

Python Implementáció

Rekurzív Megoldás

def hanoi_tower(n, source, target, auxiliary):
    """
    Hanoi tornyai probléma rekurzív megoldása.
    
    Args:
        n: A korongok száma.
        source: Az induló oszlop neve.
        target: A céloszlop neve.
        auxiliary: A segédoszlop neve.
    """
    if n == 1:
        print(f"Mozgasd a(z) {n}. korongot {source} oszlopról {target} oszlopra.")
        return
    # 1. Az n-1 korongot áthelyezzük a segédoszlopra
    hanoi_tower(n-1, source, auxiliary, target)
    # 2. Az n-edik korongot áthelyezzük a céloszlopra
    print(f"Mozgasd a(z) {n}. korongot {source} oszlopról {target} oszlopra.")
    # 3. Az n-1 korongot áthelyezzük a segédoszlopról a céloszlopra
    hanoi_tower(n-1, auxiliary, target, source)

# Példa használat
n = 3  # Korongok száma
hanoi_tower(n, "A", "C", "B")

Kimenet

Ha $n=3$, a kimenet:

Mozgasd a(z) 1. korongot A oszlopról C oszlopra.
Mozgasd a(z) 2. korongot A oszlopról B oszlopra.
Mozgasd a(z) 1. korongot C oszlopról B oszlopra.
Mozgasd a(z) 3. korongot A oszlopról C oszlopra.
Mozgasd a(z) 1. korongot B oszlopról A oszlopra.
Mozgasd a(z) 2. korongot B oszlopról C oszlopra.
Mozgasd a(z) 1. korongot A oszlopról C oszlopra.

Iteratív Megoldás

def hanoi_tower_iterative(n, source, target, auxiliary):
    """
    Hanoi tornyai probléma iteratív megoldása.
    
    Args:
        n: A korongok száma.
        source: Az induló oszlop neve.
        target: A céloszlop neve.
        auxiliary: A segédoszlop neve.
    """
    moves = []
    stack = [(n, source, target, auxiliary)]

    while stack:
        n, source, target, auxiliary = stack.pop()
        if n == 1:
            moves.append((source, target))
        else:
            # Hozzáadjuk a lépéseket fordított sorrendben
            stack.append((n-1, auxiliary, target, source))
            stack.append((1, source, target, auxiliary))
            stack.append((n-1, source, auxiliary, target))
    
    for i, move in enumerate(moves, start=1):
        print(f"{i}. lépés: Mozgasd a(z) korongot {move[0]} oszlopról {move[1]} oszlopra.")

# Példa használat
n = 3  # Korongok száma
hanoi_tower_iterative(n, "A", "C", "B")

Kimenet

Az iteratív megoldás kimenete ugyanaz lesz, mint a rekurzív megoldásé.

Ábrázolás és Vizualizáció

Egyszerű vizualizáció Pythonban a `turtle` könyvtár segítségével:

import turtle

def hanoi_visual(n, source, target, auxiliary, pen):
    if n == 1:
        pen.goto(target)
        pen.write(f"Mozgasd a(z) {n}. korongot {source} -> {target}")
        return
    hanoi_visual(n-1, source, auxiliary, target, pen)
    pen.goto(target)
    pen.write(f"Mozgasd a(z) {n}. korongot {source} -> {target}")
    hanoi_visual(n-1, auxiliary, target, source, pen)

# Példa használat
pen = turtle.Turtle()
pen.speed(1)
hanoi_visual(3, "A", "C", "B", pen)
turtle.done()

Alkalmazások

1. Számítástechnika:

  - Rekurzió alapelveinek tanítása.
  - Veremstruktúrák működésének megértése.

1. Logisztikai problémák:

  - Tárhelyek optimalizált átszervezése.

1. Matematikai kutatások:

  - Kombinatorikai és optimalizációs problémák modellezése.

Összegzés

A **Hanoi tornyai** egyszerű probléma, amely kiválóan illusztrálja a rekurzió és az optimalizáció alapelveit. A Pythonban történő implementáció mind rekurzív, mind iteratív módszerekkel könnyen megvalósítható, és alkalmas arra, hogy tanulási célokra és algoritmusfejlesztésre használjuk. A vizualizáció segít a probléma intuitív megértésében.

• angol: tower of Hanoi (en)
• német: Türme von Hanoi (de)
• orosz: Ханойская башня (ru) (Xanojskaja bašnja)

További információk

• Hanoi tornyai - Értelmező szótár (MEK)
• Hanoi tornyai - Etimológiai szótár (UMIL)
• Hanoi tornyai - Szótár.net (hu-hu)
• Hanoi tornyai - DeepL (hu-de)
• Hanoi tornyai - Яндекс (hu-ru)
• Hanoi tornyai - Google (hu-en)
• Hanoi tornyai - Helyesírási szótár (MTA)
• Hanoi tornyai - Wikidata
• Hanoi tornyai - Wikipédia (magyar)