递归解决汉诺塔问题
本帖最后由 三滑稽甲苯 于 2021-1-23 22:17 编辑1. 汉诺塔介绍
你要将所有的盘子从TOWER 1移动到TOWER 3
你每次只能移动一个盘子。
游戏最重要的规则是大的盘子不能放在小的盘子上面！
（简介/在线游戏：http://www.hannuota.cn/）
2. 思路
若需要将n层塔从fr移至dst, 可化解为将n-1层移至空余的位置（记为other）, 将最底下一层移至dst, 然后将other的n-1层移至dst。
根据此思路递归，即可获得结果。
3. 代码
class Tower:
def __init__(self, max):
if 1 <= max <= 9: self.max = max
else: raise ValueError('Height toooo large!')
self.data = [[], [], []]
self.step = 0
self.ans = ''
for i in range(max):
self.data.append(i + 1)
self.data.append(0)
self.data.append(0)
def show(self):
s = ''
for i in range(self.max):
s += f'{self.data}{self.data}{self.data}\n'
s += 'abc'
return s
def move(self, fr, dst):
last1 = 0; last2 = self.max - 1
for i in range(self.max):
if self.data: last1 = i; break
for i in range(self.max):
if self.data: last2 = i; break
if self.data:
if self.data < self.data:
self.data = self.data
self.data = 0
self.step += 1
self.ans += f'{fr}->{dst}\n'
return True
elif last2 == self.max - 1 and self.data == 0:
self.data = self.data
self.data = 0
self.step += 1
self.ans += f'{fr}->{dst}\n'
return True
else: return False
else: return False
def moves(self, fr, dst, depth):
if depth == 1:
return self.move(fr, dst)
else:
flag = True
other = 3 - fr - dst
flag *= self.moves(fr, other, depth - 1)
if flag: flag *= self.move(fr, dst)
if flag: flag *= self.moves(other, dst, depth - 1)
return flag
height = 9
test = Tower(height)
print(test.show())
if test.moves(0, 2, height):
print(test.ans)
print(test.show())
print(test.step)
input('Fin.')
想修改层数把最后一段代码中2的height改为想要的层数即可(1~9)。
4. 效果
学习了大神
页:
[1]