省流：没有更新完成，正在慢慢更新。
Hanoi Tower 问题本身很简单，A,B,C 三个柱子，起初每一个圆盘都在 A 上，想要全部移动到 B/C。每次只能移动最上面的，大的在小的圆盘下面。
Original Problem/原问题
考虑一个递归函数。\(hanoi(n,A,B,C)\) 代表目标是把 \(N\) 这个大小的盘子通过 B 从 A 移动到 C。
void hanoi(int n,char A,char B,char C){
if (n){
hanoi(n-1,A,C,B);
cout<<A<<"->"<<C<<endl;
hanoi(n-1,B,A,C);
}
}
步数是 \(2^n-1\)。总共状态是 \(2^n\) 个（包含最前面的）。
-
最优是 \(2^n-1\)。对于一个盘子 \(x\)，它的希望是 \(1\cdots x-1\) 都从它身上下来，它移动一下，\(1\cdots x-1\) 都再爬到他身上。没有步数的浪费，所以是最优。
-
总共状态是 \(2^n\) 个。最多 \(2^n\) 个。如果有两个重复的，一定不是最优解（可以把中间的去掉）。
一共有 \(3^n-2^n\) 个状态不能达到。
A More Abstract Way/一个更抽象的方式
因为有 \(2^n\) 个状态可以达到，就可以用长度为 \(n\) 的二进制串来表示每一个状态，一共 \(2^n\) 个。我们可以尝试用 \(+1\) 来表示一步，从 \(0\) 加到 \(2^n-1\) 就做完了。
-
如果一个 \(+1\) 不进位，就代表 \(1\) 号盘子往右移动了 \(1\) 步。
-
反之，那个从 \(0\) 变成 \(1\) 的对应的盘子，移动到它可以移动的位置。
例如：\(3\) 个盘子。
-
\(000\rightarrow 001\)：\(A\rightarrow B\)。
-
\(001\rightarrow 010\)：\(A\rightarrow C\)。
-
\(010\rightarrow 011\)：\(B\rightarrow C\)。
-
\(011\rightarrow 100\)：\(A\rightarrow B\)。
-
\(100\rightarrow 101\)：\(C\rightarrow A\)。
-
\(101\rightarrow 110\)：\(C\rightarrow B\)。
-
\(110\rightarrow 111\)：\(A\rightarrow B\)。
（\(X\rightarrow Y\) 代表 \(X\) 最上面的移动到 \(Z\)）
为什么是对的？
一个大一点的例子： \(000000\)。第一个 \(0\) 要变成 \(1\)，要经过 \(011111\rightarrow 100000\rightarrow 111111\)。对于每一位都是。也就相当于上面的盘子移开，自己移好，再把其他盘子移上来。
Change \(1\): Only Adjacent/只能相邻
现在在原问题的规定上，只能 \(A\rightarrow B,B\rightarrow C,C\rightarrow B,B\rightarrow A\)。这样，要几步呢？答案不难猜到，\(3^n-1\)。
一个盘子想要移动到最终的位置上，怎么办？
-
上面的盘子往右 \(2\) 步。
-
自己往右 \(1\) 步。
-
上面的盘子往左 \(2\) 步。
-
自己往右 \(1\) 步。
-
上面的盘子往右 \(2\) 步。
按照上面二进制的方法，这边就变成了三进制。
-
\(+1\) 不进位：\(1\) 往左/右 \(1\)。
-
反之，对应的一个盘子移动。
这种变形还有一个性质，就是一共有 \(3^n\) 个状态，它都可以达到，而且没有重复的。如果把互相可以达到的状态连一条边，从 \(AAA\) 走到 \(CCC\)，会形成一个很好看的形状。
（别人的图）
可以发现，原问题是最短路，这个，是最长路。
Change \(2\): Unreached Count/不能达到的状态
原问题中，如果我们最终全部放到 B，对于一个状态，怎么判断它能不能到？