C++ 算法：将正整数表示成 2 的幂次方和

任何一个正整数都可以用 2 的幂次方表示。例如：137 = 2^7 + 2^3 + 2^0，同时约定方次用括号来表示，即 a^b 可表示为 a(b)。由此可知，137 可表示为：2(7) + 2(3) + 2(0)，进一步：7 = 2^2 + 2 + 2^0（2^1 用 2 表示），3 = 2 + 2^0，所以最后 137 可表示为：2(2(2) + 2 + 2(0)) + 2(2 + 2(0)) + 2(0)。

又如：1315 = 2^10 + 2^8 + 2^5 + 2 + 2^0，所以 1315 最后可表示为：2(2(2 + 2(0)) + 2) + 2(2(2 + 2(0))) + 2(2(2) + 2(0)) + 2 + 2(0)。

算法实现

#include <iostream>
using namespace std;

void dfs(int n) {
    if (n == 0) {
        cout << "0";
        return;
    }
    if (n == 1) {
        cout << "2(0)";
        return;
    }
    if (n == 2) {
        cout << "2";
        return;
    }
    int k = 0;
    while ((1 << k) <= n) {
        k++;
    }
    k--;
    if (k == 1) {
        cout << "2+";
    } else {
        cout << "2(";
        dfs(k);
        cout << ")+";
    }
    dfs(n - (1 << k));
}

int main() {
    int n;
    cin >> n;
    dfs(n);
    return 0;
}

代码解释

该算法使用递归函数 dfs(n) 来实现，该函数接受一个正整数 n 作为参数，递归地将 n 分解为 2 的幂次方的形式，并输出最终结果。
函数首先判断 n 是否为 0、1 或 2，如果是则直接输出对应的表示方式。
否则，函数找到小于等于 n 的最大 2 的幂次方 (1 << k)，并将其从 n 中减去，递归地调用 dfs 函数处理剩余部分 (n - (1 << k))。
在递归处理 k 时，如果 k 等于 1，则直接输出 2+，否则输出 2(k)+。
递归结束条件是 n 等于 0，此时递归调用栈依次返回，并拼接输出最终结果。

总结

本文介绍了用 C++ 实现将任何正整数表示成 2 的幂次方和的算法，并提供了代码示例。该算法使用递归函数，将整数分解为 2 的幂次方的形式，并最终输出符合约定的表示方式。该算法简单易懂，且易于实现，适合初学者学习和理解递归算法的应用。