_09_hanoi Namespace Reference

Towers of Hanoi. More...

Functions
def	Hanoi (n, from_, to_, by_)
	Hanoi Tower. More...
def	main (argv=None)
	Main function for testing. More...

Detailed Description

Towers of Hanoi.

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. The game consists of a tower of eight disks, initially stacked in increasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, by moving only one disk at a time, and never a larger one onto a smaller.

Recurrence: \(T(h) = 2T(h-1) + 1 = 2^{h} - 1 \to O(2^{h}).\)

Author

Paulo Roma

Since

31/12/2008

See also

http://en.wikipedia.org/wiki/Tower_of_Hanoi

http://www.cut-the-knot.org/recurrence/hanoi.shtml

Function Documentation

Hanoi()

def _09_hanoi.Hanoi	(		n,
			from_,
			to_,
			by_
	)

Hanoi Tower.

A game invented by the French mathematician Edouard Lucas in 1883.

1. Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg).
2. Move the bottom disk from Src to Dst.
3. Move N-1 disks from Aux to Dst (using Src as an intermediary peg).

Parameters

n	number of disks.
from_	source peg.
to_	destination peg.
by_	intermediary peg.

Referenced by main().

main()

def _09_hanoi.main

(

argv = None

)

Main function for testing.

Parameters

argv	number of disks.

References Hanoi(), and _01d_dec2bin.input.