GESP 五级 · GESP 202509 C++ 五级 第 23 题

下面代码采用分治算法求解标准 3 柱汉诺塔问题，时间复杂度为 $O(n \log n)$。

void move(vector<int> &src, vector<int> &tar) {
    int pan = src.back();
    src.pop_back();
    tar.push_back(pan);
}

void dfs(int n, vector<int> &src, vector<int> &buf, vector<int> &tar) {
    if (n == 1) {
        move(src, tar);
        return;
    }

    dfs(n - 1, src, tar, buf);
    move(src, tar);
    dfs(n - 1, buf, src, tar);
}

void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
    int n = A.size();
    dfs(n, A, B, C);
}

汉诺塔递归：将n个盘从A移到C，借助B。递归式：先将n-1个盘从A移到B（借助C），再将第n个盘从A移到C，最后将n-1个盘从B移到C（借助A）。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递归算法｜分治复杂度｜汉诺塔

1. 🎯 考纲定位

GESP五级 算法模块 递归与分治（分治策略）。命题人卡住的是考生对汉诺塔时间复杂度的经典记忆误区——很多人把汉诺塔和归并排序、快速排序混淆，误以为分治递归就是 $O(n \log n)$。