经典问题
程序员文章站
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)
上一篇: 【数据结构】哈夫曼树