汉诺塔 (Tower of Hanoi)

问题

有 a, b, c 三个塔座，在塔座 a 上共叠有 n 个圆盘，这些圆盘自下而上，由大到小叠放。 要求将塔座 a 上的所有圆盘移到塔座 b 上，c 作为辅助塔，规则有二：

• 每次只能移动一个圆盘
• 大的圆盘不能压在小的圆盘之上

思路

将所有圆盘 (n) 从 a 移动到 b 相当于

1. 将 n - 1 个圆盘（除了最大的）从 a 移动到 c
2. 将最大的圆盘从 a 移动到 b
3. 将 c 上的所有圆盘 (n - 1) 移动到 b

边界：
a 上没有圆盘

这样就将规模为 n 的问题分解成了 2 个规模为 n - 1 的问题

代码

为了验证代码，我去玩了汉诺塔游戏 :)

(define (hanoi n a b c)
  (cond [(> n 0)
         (hanoi (- n 1) a c b)
         (printf "~a ~a ~a~n" a '-> b)
         (hanoi (- n 1) c b a)]))

(hanoi 5 'a 'b 'c)