经典问题

1.汉诺塔

 

# 汉诺塔
# 思路:把最底下的盘子看成一个整体,除了最底下的盘子以外的盘子(n-1)看作一个整体,
# 目标是:原来的盘子都在a,现在要移动到c.
# 移动的顺序是:
# ①先把(n-1)从a经过c移动到b
# ②再把a上最后一个大盘子直接移动到c,这就放好了最后一个盘子
# ③再把(n-1)从b经过a移动到c
# (n, a, b, c)表示从a经过b移动到c
# (n, b, a, c)表示从b经过a移动到c
def hanoi(n, a, b, c):#n是n个盘子,a,b,c是三个柱子
    if n>0:
        hanoi(n-1, a, c, b)   #第一步,把n-1部分从a经过c移动到b,这一步需要走两步,先经过c,再到b,所以可以用递归
        print("把 %s 移动到%s" % (a, c),) #第二步,将a剩下的最后一个盘子直接移动到c,不用经过b,所以,他不用再递归,直接记录步骤加一即可
        hanoi(n-1, b, a, c)  #第三步,将n-1部分从b经过a,移动到c,这里又需要递归了,所以又调用了自己,一直递归到这个柱子没了盘子就停止

print('每次移动都只移动一个盘子')
hanoi(3, 'a', 'b', 'c')
#这里的3是盘子总数,abc分别代表一个柱子
# 每打印一行,便进行一次操作,行数就是汉诺塔移动的次数

 

计数版

i=0
def hanoi(l,a,b,c):
    global i
    if l>0:
        hanoi(l-1,a,c,b)
        print('从 %s 移动到 %s'%(a,c) )
        i+=1
        hanoi(l-1,b,a,c)
hanoi(3,'a','b','c')
print(i)