题目描述
任何一个正整数都可以用 $2$ 的幂次方表示。例如 $\displaystyle 137=2^7+2^3+2^0$ 。
同时约定次方用括号来表示，即 $\displaystyle a^b$ 可表示为 $a(b)$（ $\displaystyle a^b$ 为a的b次方）。
由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$ 。
进一步：
$\displaystyle 7=2^2+2+2^0$ ( $\displaystyle 2^1$ 用 $2$ 表示)，并且 $\displaystyle 3=2+2^0$ ，
所以最后 $137$ 可表示为：$2(2(2)+2+2(0))+2(2+2(0))+2(0)。$
又如 $\displaystyle 1315=2^{10}+2^8+2^5+2+1$ ,
所以 $1315$ 最后可表示为:
$ 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$ 。
整体思路
看到这道题，相信很多人都第一时间想到了递归。虽然很多大佬用二进制也能完成这道题，但是递归无疑是最容易理解的一种方式。 我们不妨定义一个函数 void print(int k){}，用这个函数来打印出 $k$ 的 $2$ 的幂次方表示。
具体实现
我们从 $1$ 开始尝试： 当 $k=1$ 时，应输出 ” $2(0)$ “；
当 $k=2$ 时，应输出 ” $2$ “；
当 $k=3$ 时，应输出 ” $2+2(0)$ “；
当 $k=4$ 时，应输出 ” $2(2)$ “；
当 $k=5$ 时，应输出 ” $2(2)+2(0)$ “；
$\cdots$
首先，我们发现输出的结果都是由“ $2(0)$ ”和“ $2$ ”组成的，所以递归的终止条件就是 $k=1$ 或 $2$ 。
其次， $k>3$ 后，结果都是由多部分组成的（除了 $2$ 的整数幂），所以不妨先利用循环枚举，将 $k$ 分解为多个 $2$ 的整数幂形式，存在数组中，以便输出。
最后，在输出前几项时，应紧跟着输出 ‘$+$’ ，而最后一项不需要输出 ‘$+$’。
代码实现
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
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
using namespace std;
int pow[17]; // 存储2的所有整数幂的值，数据最大范围是2×10^4，而2^15约等于32768
void print(int k)
{
int t = 15;
int a[17]; // 存储k分解后的2的整数幂
int len = 0; // 计录数组a的长度
memset(a, 0, sizeof(a));
while (k > 0) // 循环将k分解为2的整数幂，并存入数组a中
{
if (k >= pow[t])
{
a[++len] = t; // 存入指数
k -= pow[t];
}
t--;
}
for (int i = 1; i <= len; i++) // 循环递归（最后一项不需要‘+’）
{
if (a[i] == 0) // 如果这一项指数为0，输出”2（0）“
cout << "2(0)";
else if (a[i] == 1) // 如果这一项指数为0，输出”2“
cout << "2";
else
{
cout << "2(";
print(a[i]); // 其他情况，输出"2（a[i])"
cout << ")";
}
if (i != len) // 最后一项不需要输出'+'
cout << '+';
}
return;
}
int main()
{
pow[0] = 1;
for (int i = 1; i <= 15; i++)
pow[i] = 2 * pow[i - 1]; // 提前计算2的整数幂，减少计算量
int n;
cin >> n;
print(n);
cout << endl;
return 0;
}
