LintCode Python 简单级题目 227.用栈模拟汉诺塔问题

原题描述：

在经典的汉诺塔问题中，有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子。要求盘子必须按照从小到大的顺序从上往下堆 （如，任意一个盘子，其必须堆在比它大的盘子上面）。同时，你必须满足以下限制条件：

(1) 每次只能移动一个盘子。

(2) 每个盘子从堆的顶部被移动后，只能置放于下一个堆中。

(3) 每个盘子只能放在比它大的盘子上面。

请写一段程序，实现将第一个堆的盘子移动到最后一个堆中。

您在真实的面试中是否遇到过这个题？

Yes

样例

标签

栈

题目分析

将整个移动过程分为3个步骤：

状态0:　　　　　　　　　　　　　　　　　　　状态1:　　　　　　　　　　　　　　

　　towers[0] : [n,n-1,...,2,1,0]　　　　　　　　 towers[0] : [n]　　

　　towers[1] : []　　　　　　　　　　　　　　　　　towers[1] : [n-1,n-2,...,2,1,0]

　　towers[2] : []　　　　　　　　　　　　　　　　　towers[2] : []　　　　　　　　　　　　　　

状态2:　　　　　　　　　　　　　　　　　　　　状态3:

　　towers[0] : []　　　　　　　　　　　　　　　　 towers[0] : []

　　towers[1] : [n-1,n-2,...,2,1,0]　　　　　　　 towers[1] : []

　　towers[2] : [n]　　　　　　　　　　　　　　　　towers[2] : [n,n-1,...,2,1,0]

一、状态0 ——> 状态1，其实就是将原塔上的n-1块盘子移动到过程塔上；

二、状态1 ——> 状态2，将原塔的第n块盘子移动到目标塔上；

三、状态2 ——> 状态3，其实就是简化的原题要求，到这里就是重复0-1-2过程；

　　由于目标塔上的盘子大小是n，大于剩下的所有盘子，所以等同于空塔~

　　这里只是原塔变成了过程塔，目标塔还是目标塔，过程塔变成了原塔；

状态2:　　　　　　　　　　　　　　　　　　　　变化状态2:

　　towers[0] : []　　　　　　　　　　　　　　　　 　　 towers[1] : [n-1,n-2,...,2,1,0]

　　towers[1] : [n-1,n-2,...,2,1,0]　　　　　　　　 　towers[0] : []

　　towers[2] : [n]　　　　　　　　　　　　　　　　　　 towers[2] : [n]

然后重复此过程，直至n=0：

　　状态0 ——> 状态1——> 状态2（另一种形式的状态0）——> 状态1——> 状态2——> 。。。——> 状态3

当n=0时，即达到状态3.

参考分析资料:

　　http://www.cnblogs.com/shenxiaoquan/p/5914896.html

源码实现：

class Tower(object):
    # create three towers (i from 0 to 2)
    def __init__(self, i):
        self.disks = []
        
    # Add a disk into this tower
    def add(self, d):
        if len(self.disks) > 0 and self.disks[-1] <= d:
            print "Error placing disk %s" % d
        else:
            self.disks.append(d);
        
    # @param {Tower} t a tower
    # Move the top disk of this tower to the top of t.
    def move_top_to(self, t):
        # Write your code here
        if len(self.disks) > 0:
            t.disks.append(self.disks.pop())
         
    # @param {int} n an integer
    # @param {Tower} destination a tower
    # @param {Tower} buffer a tower
    # Move n Disks from this tower to destination by buffer tower
    def move_disks(self, n, destination, buffer):
        # Write your code here
        if n == 0:
            return
        if n == 1:
            self.move_top_to(destination)
        else:
            # 状态0-状态1，实现将除了n的其他盘子移动到buffer塔上
            self.move_disks(n-1,buffer,destination)
            # 状态1-状态2，实现将最后一个n盘移动到destination塔上
            self.move_top_to(destination)
            # 状态2-状态3(0)，转化buffer塔为原塔，将剩下的n-1个盘子移动到destination塔上
            buffer.move_disks(n-1,destination,self)

    def get_disks(self):
        return self.disks

"""
Your Tower object will be instantiated and called as such:
towers = [Tower(0), Tower(1), Tower(2)]
for i in xrange(n - 1, -1, -1): towers[0].add(i)
towers[0].move_disks(n, towers[2], towers[1])
print towers[0], towers[1], towers[2]
"""