算法：汉诺塔问题的非递归解法

题目：

有三根柱子，从左到右排列，编号分别是0、1、2。0号柱子上有n个盘子，从上到下，盘子依次增大，编号为1、2、3、···、n。现在需要将0号柱子上的盘子搬到右方编号为2的柱子上。有三条规则：

1. 一次搬一只盘子。
2. 每根柱子只有最上面的盘子可被搬动。
3. 大盘子不可置于小盘子的上方。

思路：

本题是经典问题，常规解法就是使用递归。本次尝试采用for循环来解决（思路来自《图解算法》(俞征武著)一书）。通过观察，发现要把n个盘子从0柱移到2柱需要移动2ⁿ-1次。所以一个循环,i从1到2ⁿ-1。

1. 计算最大的k,使得i=2^k * y（故本次将搬动第k+1号盘子）
2. 当n为偶数且k+1为奇数时，移动第k+1号盘子从当前的s柱子半岛第(s+1)%3柱子
   当n为偶数且k+1为偶数时，移动第k+1号盘子从当前的s柱子半岛第(s-1)%3柱子
   当n为奇数且k+1为奇数时，移动第k+1号盘子从当前的s柱子半岛第(s-1)%3柱子
   当n为奇数且k+1为偶数时，移动第k+1号盘子从当前的s柱子半岛第(s+1)%3柱子

代码：

class Hanota {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = (int)A.size();
        if (n == 1) {
            C.emplace_back(A.back());
            return;
        }
        if (n == 2) {
            B.emplace_back(A.back());
            A.pop_back();
            C.emplace_back(A.back());
            C.emplace_back(B.back());
            B.pop_back();
            A.pop_back();
            return;
        }
        int r = pow(2,n)-1;
        vector<int> nPillar(n+1,0);
        vector<vector<int>> tmp;
        tmp.emplace_back(A);
        tmp.emplace_back(B);
        tmp.emplace_back(C);
        
        for(int i = 1; i <= r;i++) {
            int k = maxK(i);
            
            int s = nPillar[k+1];
            int d = 0;
            
            if (n%2 == 0 && (k+1)%2 == 1) {
                d = (s+1)%3;
            }
            else if (n%2 == 0 && (k+1)%2 == 0) {
                if (s == 0) {
                    d = 2;
                }
                else {
                    d = (s-1)%3;
                }
            }
            else if (n%2 == 1 && (k+1)%2 == 1) {
                if (s == 0) {
                    d = 2;
                }
                else {
                    d = (s-1)%3;
                }
            }
            else if (n%2 == 1 && (k+1)%2 == 0) {
                d = (s+1)%3;
            }
            int opNum = tmp[s].back();
            tmp[d].emplace_back(opNum);
            tmp[s].pop_back();
            nPillar[k+1] = d;
        }
    }
    //计算最大的k
    int maxK(int num) {
        int i = 0;
        int powr = 1;
        while (num >= powr && num%powr == 0) {
            i++;
            powr = pow(2, i);
        }
        return powr == 1 ? i : i-1;
    }
};