【NOIP1998】幂次方解题：递归与位运算的巧妙结合（附代码解析）

一、题目解读

1998年NOIP普及组题目“幂次方”（对应洛谷P1010）要求将给定整数N转换为2的幂次方和的表达式，例如N=5应输出“2+2(2)”。题目考察对数字分解、递归算法及位运算的理解，需找到高效的分解方法并生成规范的表达式。

二、解题思路

递归+位运算的策略：

1. 递归分解核心：将整数N分解为多个2的幂次方之和（如N=7 → 2² + 2¹ + 2⁰）。

2. 位运算优化：利用左移运算符（1 << i）快速计算2的i次方，从高位到低位遍历，判断N是否包含当前幂次，若包含则递归处理剩余部分。

3. 表达式拼接：递归调用生成子表达式，按规则添加括号和加号。

三、解题步骤

1. 边界处理：当N=0/1/2时直接返回特殊结果。

2. 分解循环：从2²⁰开始向下遍历，若N≥2ⁱ，则将i加入幂次列表，并更新N减去当前幂次。

3. 递归生成子项：对每个幂次i，若i=1则直接输出“2”，否则递归调用DFS(i)生成子表达式，如“2(2(0))”。

4. 拼接结果：用vector存储幂次，遍历时添加“+”分隔，最后组合成完整表达式。

四、代码与注释

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 递归函数：将n转换为2的幂次方和表达式
string dfs(int n) {
    if (n == 0) return "0";          // 边界：0直接返回
    if (n == 1) return "2(0)";       // 1的特殊处理
    if (n == 2) return "2";          // 2的特殊处理

    vector<int> powers;              // 存储分解的幂次
    int temp = n;                    // 临时变量记录剩余值

    // 从最高次方开始遍历分解
    for (int i = 20; i >= 0; i--) {
        if (temp >= (1 << i)) {       // 若剩余值≥2ⁱ，加入幂次列表并减去对应值
            powers.push_back(i);
            temp -= (1 << i);
        }
    }

    string res;                      // 结果表达式
    for (int i = 0; i < powers.size(); i++) {
        int p = powers[i];
        if (p == 1) {                // 幂次为1时直接输出"2"
            res += "2";
        } else {                     // 否则递归生成子表达式
            res += "2(" + dfs(p) + ")";
        }
        if (i!= powers.size() - 1) {  // 非最后一个项添加"+"分隔
            res += "+";
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;                      // 输入整数N
    cout << dfs(n) << endl;        // 输出表达式
    return 0;
}

五、总结

该解法巧妙结合递归与位运算，通过从高位向低位分解，避免了暴力枚举，时间复杂度为O(logN)。递归深度取决于N的二进制位数，而位运算使分解过程简洁高效。代码结构清晰，递归边界与表达式拼接逻辑严谨，是学习递归算法与位运算结合的典型案例。