欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

经典问题

程序员文章站 2022-05-04 08:48:46
1.汉诺塔 # 汉诺塔 # 思路:把最底下的盘子看成一个整体,除了最底下的盘子以外的盘子(n-1)看作一个整体, # 目标是:原来的盘子都在A,现在要移动到C. # 移动的顺序是: # ①先把(n-1)从A经过C移动到B # ②再把A上最后一个大盘子直接移动到C,这就放好了最后一个盘子 # ③再把( ......

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)