分治与递归的完美结合:NOIP1998幂次方问题深度解析与代码实现
一、问题描述与算法思路
幂次方问题要求将任意正整数表示为2的幂次方分解形式,例如137表示为2(7)+2(3)+2(0),再进一步分解为2(2(2)+2+2(0))+2(2+2(0))+2(0)。这个问题完美展示了分治算法的实际应用场景。
二、完整代码解析
#include <iostream> #include <string> #include <vector> using namespACe std; // 递归分解函数 string dfs(int n) { // 处理基本情况 if (n == 0) return "0"; // 2^0的特殊表示 if (n == 1) return "2(0)"; // 2^1的递归终止情况 if (n == 2) return "2"; // 2^1的简化表示 vector<int> powers; // 存储分解出的幂次 int temp = n; // 临时变量保存n值 // 将n分解为2的幂次和 for (int i = 20; i >= 0; i--) { // 从高到低检查每个可能的幂次 if (temp >= (1 << i)) { // 使用位运算检查当前幂次是否存在 powers.push_back(i); // 记录存在的幂次 temp -= (1 << i); // 减去已分解部分 } } // 构建结果字符串 string res; for (int i = 0; i < powers.size(); i++) { int p = powers[i]; // 当前处理的幂次 if (p == 1) { res += "2"; // 2^1直接表示为2 } else { res += "2(" + dfs(p) + ")"; // 递归处理指数部分 } // 添加加号分隔符(最后一个不加) if (i != powers.size() - 1) { res += "+"; } } return res; } int main() { int n; cin >> n; cout << dfs(n) << endl; // 调用分解函数并输出结果 return 0; }
三、关键算法要点解析
四、算法优化建议
五、常见错误与调试技巧
递归终止条件不完整导致无限递归
幂次分解顺序错误导致结果不正确
字符串拼接时格式错误(括号不匹配)
位运算边界条件处理不当
原创内容 转载请注明出处