C++ 正整数 2 的幂次方表示 算法实现

C++ 正整数 2 的幂次方表示算法实现

本文将介绍如何使用 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^1 + 2^0  (2^1 用 2 表示)
3 = 2^1 + 2^0

所以最后 137 可表示为：

2(2(2) + 2 + 2(0)) + 2(2 + 2(0)) + 2(0)

又如：

1315 = 2^10 + 2^8 + 2^5 + 2^1 + 2^0

所以 1315 最后可表示为：

2(2(2 + 2(0)) + 2) + 2(2(2 + 2(0))) + 2(2(2) + 2(0)) + 2 + 2(0)

输入:

一个正整数 n (n ≤ 20000)。

输出:

一行，符合约定的 n 的 0，2 表示（在表示中不能有空格）。

思路:

递归求解，每次将 n 表示成 2 的幂次方的和，然后递归处理即可。

C++ 代码:

#include <iostream>
using namespace std;

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

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

代码解析:

• solve(int n) 函数实现递归求解。
• k 表示 2 的幂次方的指数，从 0 开始，不断加 1 直到大于等于 n 为止。
• 当 k 大于 1 时，输出 2(k)；当 k 等于 1 时，输出 2；当 k 等于 0 时，输出 2(0)。
• 递归调用 solve(n - (1 << k))，将 n 减去 2 的 k 次方，并继续求解。

代码示例:

输入：137
输出：2(2(2)+2+2(0))+2(2+2(0))+2(0)

输入：1315
输出：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)