Discuss / Python / 我的思路
Back

我的思路

Topic source

大梦shake

#1 Created at ... [Delete] [Delete and Lock User]

哈哈，没有参考网上的算法，自己从 n = 4 一步步画图推导出来了，说下我自己的理解。

代码：

def move(n, a, b, c):
    if n == 1:
        print('%s --> %s' % (a, c))
    else:
        move(n-1, a, c, b)
        print('%s --> %s' % (a, c))
        move(n-1, b, a, c)

思路：

由于规则是小能压大而大不能压小，所以不论中间步骤如何，最后每个盘子落到C肯定是从大到小的顺序。所以肯定是第n个先落到C，而由于第n个是最大的，所以有且只有一种方法把第n个落到C：先把上面n-1个全部移到B，然后才能把第n个落到C。

由此把整个过程拆分为三步：

  1. 把上面n-1个从A移到B（向下递归）
  2. 把第n个从A移到C（实际移动的一步）
  3. 最后把B上的n-1个从B移到C（向下递归）

用函数表示就是： move(n, a, b, c) = move(n-1, a, c, b) + move(1, a, b, c) + move(n-1, b, a, c)

注意 a、b、c 的顺序。

这三步实质上是进行了两次递归和1次实际移动。这样递归下去，形成了一个树状递归结构，所以最终步数是： 1 + 2 + 4 + 8 + ... + 2**（n-1） = 2**n -1

Min张小哥

#2 Created at ... [Delete] [Delete and Lock User]

思路差不多理解了，可是为啥打印出来的东西不理解是什么意思？求大神帮解答。

Min张小哥

#3 Created at ... [Delete] [Delete and Lock User]

理解了，谢谢撸主。

  • 1

Reply