递归解决汉诺塔问题

三滑稽甲苯

1. 汉诺塔介绍
你要将所有的盘子从TOWER 1移动到TOWER 3
你每次只能移动一个盘子。
游戏最重要的规则是大的盘子不能放在小的盘子上面！
（简介/在线游戏：http://www.hannuota.cn/）

简介

---

2. 思路
若需要将n层塔从fr移至dst, 可化解为将n-1层移至空余的位置（记为other）, 将最底下一层移至dst, 然后将other的n-1层移至dst。
根据此思路递归，即可获得结果。

思路

---

3. 代码

代码

[Python] 纯文本查看 复制代码

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[0].append(i + 1)
            self.data[1].append(0)
            self.data[2].append(0)
    
    def show(self):
        s = ''
        for i in range(self.max):
            s += f'{self.data[0][i]}  {self.data[1][i]}  {self.data[2][i]}\n'
        s += 'a  b  c'
        return s
    
    def move(self, fr, dst):
        last1 = 0; last2 = self.max - 1
        for i in range(self.max):
            if self.data[fr][i]: last1 = i; break
        for i in range(self.max):
            if self.data[dst][i]: last2 = i; break
        if self.data[fr][last1]:
            if self.data[fr][last1] < self.data[dst][last2]:
                self.data[dst][last2 - 1] = self.data[fr][last1]
                self.data[fr][last1] = 0
                self.step += 1
                self.ans += f'{fr}->{dst}\n'
                return True
            elif last2 == self.max - 1 and self.data[dst][last2] == 0:
                self.data[dst][last2] = self.data[fr][last1]
                self.data[fr][last1] = 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. 效果

效果

糯米君

学习了大神