首页 > itarticle > recursion: hanoi tower

recursion: hanoi tower

admin 11月 12, 2020 0

It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2[^n] - 1, where n is the number of disks.

Solution : 

1
2
3
4
5
6
7
8
9
10
11
12
 
def hanoi(n, x, y, z):
    # n is for number of disk, x,y,z represent the three stacks
    if n == 1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1, x, z, y) # move n-1 disks from x to z
        print(x, ' --> ', z) # move the bottom disk from x to z
        hanoi(n-1, y, x, z) # move n-1 disks from y to z
        

n = int(input('Pls enter the number of disk:'))
hanoi(n, 'X', 'Y', 'Z')

Add the counts :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
# move n disks from x to z
steps = 0
def move(n, x, y):
    global steps
    steps += 1
    print('Move', n, 'disks', x, ' --> ', y)
def hanoi(n, x, y, z):
    # n is for number of disk, x,y,z represent the three stacks
    if n == 1:
        move(n, x, z)
    else:
        hanoi(n-1, x, z, y) # move n-1 disks from x to y by z
        move(n, x, z) # move the bottom disk from x to z
        hanoi(n-1, y, x, z) # move n-1 disks from y to z by x
       

n = int(input('Pls enter the number of disk:'))
hanoi(n, 'X', 'Y', 'Z')
print('steps: ', steps)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能