汉诺塔问题采用递归法分析

问题抽象

f(n, a, b, c)表示将n个盘子(从上到下分别记作1,2,3...n)从a柱借助b柱移动到c柱

递归公式

f(n, a, b, c) = f(n - 1, a, c, b) + "mov number n to c" + f(n - 1, b, a, c)

f(1, a, b, c) = "mov number 1 to c"

说明：这里的等号与加号为抽象表示，加号不具有交换律，加号表示先完成左边，再完成右边
如果需要计算移动次数的话，f(n - 1, a, c, b)与f(n - 1, b, a, c)是相等的，所以f(n) = 2f(n-1) + 1, f(1) = 1
注意点

将问题由F(n)缩减到F(n-1)的时候，一定要考查F(n-1)是否与F(n)等价。

错误示例：
f(n, a, b, c) = "mov number 1 to b" + f(n - 1, a, b, c) + "mov number 1 to c"

错误原因：将1号盘移动到b柱后，f(n - 1, a, b, c)与f(n, a, b, c)是不等价的，
因为这时b上放了个1号盘，1号盘上不能再放任何盘，要将n-1个盘从a借助b移动到c是行不通的

class Solution {
public:    
    void search(int n, const string &src, const string &by, const string &dest)
    {
        string str("move from " + src + " to " + dest);
        if (n == 1)
        {
            m_strvec.push_back(str);
            return;
        }

        search(n - 1, src, dest, by);
        m_strvec.push_back(str);
        search(n - 1, by, src, dest);
    }

    vector<string> getSolution(int n) {
        m_strvec.clear();
        if (n > 0)
        {
            search(n, "left", "mid", "right");
        }

        return m_strvec;
    }

private:
    vector<string> m_strvec;
};