Hanois tårn

Model af Hanoi's Tårn
Animeret Hanoi's Tårn løsning med 3 skiver.
Animeret Hanoi's Tårn løsning med 4 skiver.

Hanois tårn eller Hanois Tårne (eng. The Tower(s) of Hanoi) eller Brahmas tårn (eng. The Tower of Brahma) er et berømt matematisk hjernevrider opfundet af den franske matematiker Lucas Édouard. Spillet foregår på et stativ med tre stående lodrette pinde. På den første pind er der monteret et antal ringe med aftagende radius. Målet med spillet er at flytte hele stakken over på den tredje pind, hvor man hele tiden skal opfylde følgende to regler:

  • du må kun flytte en ring ad gangen
  • på hver eneste pind må der aldrig være en større ring på en mindre

Med 3 ringe kan hjernevrideren løses med 7 flytninger. Det minimale antal nødvendige flytninger til at løse Hanois Tårne er 2^n − 1, hvor n er antallet af ringe.

Eksempel: Hvis man vil flytte 64 ringe i Hanois tårn og hver flytning tager 1 sekund, så er alle ringe flyttet efter 590.000.000.000 år

Løsningsteknik

Novicer har tit problemer med at løse Hanois tårn, hvis der ikke er ganske få skiver. Følgende teknik virker dog generelt, til at flytte et antal (n) skiver fra pind A til pind B via pind C:

  1. n-1 skiver flyttes (hvis n>1) fra pind A til pind C (ved hjælp af denne teknik).
  2. Skive n flyttes fra pind A til pind B.
  3. De n-1 skiver flyttes atter (hvis n>1) fra pind C til pind B (igen ved hjælp af denne teknik).

Det forhold, at teknikken benytter sig selv, kaldes rekursion.


Commons-logo.svg
Wikimedia Commons har medier relateret til:

Medier brugt på denne side

Tower of Hanoi 4.gif
Forfatter/Opretter:

André Karwath aka Aka

, Licens: CC BY-SA 2.5
This animation shows the game "Tower of Hanoi" solution with four discs. There is also a version with three discs.
Tower of Hanoi.jpeg
Forfatter/Opretter: unknown, Licens: CC BY-SA 3.0
Tower of Hanoi.gif
Forfatter/Opretter:

André Karwath aka Aka

, Licens: CC BY-SA 2.5
This animation shows the solution of the game "Tower of Hanoi" with three discs. There is also a version with four discs.