问题求解II-HW04 题解
Problem A: Hanoi Tower
- 输出 $n$ 个盘子的汉诺塔的移动序列。
- $n\leq 15$。
令 $seq(n, a, b, c)$ 表示将 $n$ 个盘子从 $a$ 柱借助 $b$ 柱移到 $c$ 柱的序列，那么
$$ seq(n, a, b, c)=seq(n-1, a, c, b) + move(n, a, c) + seq(n-1, b, a, c) $$
Problem B: 数列
- 求 Fibonacci 数列的第 $n$ 项。
- $n\leq 10^9$。
求 Fibonacci 数列有经典的利用矩阵快速幂加速的手法，可以参考 这篇文章。