The Magnetic Tower of Hanoi

Download 2.78 Mb.

Page	2/20
Date	23.04.2018
Size	2.78 Mb.
	#45758

1 2 3 4 5 6 7 8 9 ... 20

. (1)
Disk numbering is done of course from bottom to top and as Equation 1 states - the smallest disk (

), like the least significant bit in a "binary speedometer", makes the largest number of moves.

The total number of moves

is given by the sum -

. (2)
Table 1 lists the (minimum) number of moves of each disk (Equation 1) and the total (minimum) number of moves required to solve the classical ToH puzzle (Equation 2) for the first eight stack heights.

k N	1	2	3	4	5	6	7	8	SUM	2^N - 1
1	1								1	1
2	1	2							3	3
3	1	2	4						7	7
4	1	2	4	8					15	15
5	1	2	4	8	16				31	31
6	1	2	4	8	16	32			63	63
7	1	2	4	8	16	32	64		127	127
8	1	2	4	8	16	32	64	128	255	255

Directory: ~dechter -> courses
courses -> Ideas for projects 276-2017: Come up with your own idea. Must be relevant to the class

Download 2.78 Mb.

Share with your friends:

1 2 3 4 5 6 7 8 9 ... 20