题目链接：https://www.lintcode.com/problem/tower-of-hanoi/description
题目大意
经典递归问题。
分析
由于是经典问题了，这里不讨论用递归实现，也不讨论用栈模拟实现，只讨论纯迭代实现。
首先用 L, M, R 来标记左柱子，中柱子，右柱子。
我们知道汉诺塔问题与二进制是密不可分的，“n-圆盘汉诺塔问题”最少只需要$2^n - 1$步，而且如果 n 为奇数，第一步必然是 L->R；如果 n 为偶数，第一步必然是 L->M。
现在我们定义三个操作，每个操作相当于走一步：
- 把 M 标记和 R 标记互换，执行 L->R。
- 把 L 标记和 M 标记互换，执行 L->R。
- 把 L 标记和 M 标记互换，把 M 标记和 R 标记互换，执行 L->R。
于是这个问题可以这样解决，去掉第一步，还剩$2^n - 2$步，如果我们把走两步算作一大步，那么还剩$2^{n - 1} - 1$大步，我们令$i:1\rightarrow2^{n - 1} - 1$依次模拟每个大步，如果 i 的最低 2 进制位的位置是偶数位置时，就执行 2 次操作 3，否则执行 1 次操作 1 和 1 次操作 2。
神奇的是，这样做居然是可行的。
PS：我是不知道为啥，我是闲着无聊找规律找到的。
代码如下
class Solution {
public:
string L = "A", M = "B", R = "C";
vector< string > ans;
/**
* @param n: the number of disks
* @return: the order of moves
*/
vector<string> towerOfHanoi(int n) {
if(n % == ) swap(M, R);
ans.push_back(step(L, R));
n = ((( << n) - ) >> );
for(int i = ; i <= n; ++i) {
// 如果i的最低2进制位的位置是偶数，就执行2次操作3，否则执行1次操作1和一次操作2
if(__builtin_ffs(i) % == ) {
op3();
op3();
}
else {
op1();
op2();
}
}
return ans;
}
inline string step(string x, string y) {
return "from " + x + " to " + y;
}
inline void op1() {
swap(M, R);
ans.push_back(step(L, R));
}
inline void op2() {
swap(L, M);
ans.push_back(step(L, R));
}
inline void op3() {
swap(M, L); swap(R, M);
ans.push_back(step(L, R));
}
};