【P1010 [NOIP1998 普及组] 幂次方】

[NOIP1998 普及组] 幂次方

问题描述

给定一个正整数 $n$，我们希望找到一种方式，将它表示为 $2$ 的幂次方的和。例如，对于 $137$，可以表示为 $2^7+2^3+2^0$，或者按照约定的方式 $2(7)+2(3)+2(0)$。

用括号来表示幂次方，即 $a^b$ 可以表示为 $a(b)$。例如，$7$ 可以表示为 $2^2+2+2^0$，其中 $2^1$ 用 $2$ 表示，这可以写成 $2(2+2(0))+2$。

解决方法

使用递归的方式来解决这个问题。首先找到最大的 $2^k$，其中 $k$ 是满足 $2^k\le n$ 的最大整数。然后将 $n$ 表示为 $2^k$ 和一个小于 $2^k$ 的余数的和。这个过程可以递归进行，直到余数为 $0$。

#include
using namespace std;

void search(int n) {
    if (n != 0) {
        int i = 1, q = 0;
        while (i <= n) {
            i *= 2;
            q++;
        }
        q--;
        i /= 2;
        if (q == 0 || q == 2)
            cout << "2(" << q << ")";
        else if (q == 1)
            cout << "2";
        else {
            cout << "2(";
            search(q);
            cout << ")";
        }
        n -= i;
        if (n != 0) {
            cout << "+";
            search(n);
        }
    }
}

int main() {
    int n;
    cin >> n;
    search(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

输入与输出

输入是一个正整数 $n$，表示我们要表示的数。

输出是满足约定的 $n$ 的表示，其中没有空格。

示例

输入示例

1315
1

输出示例

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