四柱汉诺塔问题

题目描述

汉诺塔问题，条件如下：

1. 这里有 A、B、C 和 D 四座塔。
2. 这里有 n 个圆盘，n 的数量是恒定的。
3. 每个圆盘的尺寸都不相同。
4. 所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。
5. 我们需要将所有的圆盘都从塔 A 转移到塔 D 上。
6. 每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。

请你求出将所有圆盘从塔 A 移动到塔 D，所需的最小移动次数是多少。

输入格式

没有输入。

输出格式

对于每一个整数 n，输出一个满足条件的最小移动次数，每个结果占一行。

输入输出样例

输入样例

没有输入

输出样例

1
3
5
9
13
17
25
33
41
49
65
81

限制条件

• $1 \le n \le 12$
• 对于每个 $n$，输出对应的最小移动次数

背景说明

这是经典的汉诺塔问题的扩展版本。传统的汉诺塔有三根柱子（A、B、C），而本题有四根柱子（A、B、C、D），这显著减少了完成移动所需的最少步数。

对于三柱汉诺塔，移动 $n$ 个圆盘的最小步数是 $2^n - 1$。
对于四柱汉诺塔，最小步数由以下递推公式给出： $f[n] = \min\limits_{1 \le k < n} \{ 2 \times f[k] + g[n-k] \}$
其中 $g[m]$ 表示在三根柱子上移动 $m$ 个圆盘的最小步数，即 $g[m] = 2^m - 1$。