【题目链接】
ybt 1208：2的幂次方表示
OpenJudge NOI 2.2 8758:2的幂次方表示
洛谷 P1010 [NOIP1998 普及组] 幂次方
【题目考点】
1. 递归
【解题思路】
- 递归问题：将数字k转为2的幂次方表示的字符串
- 递归关系：
二进制按位权展开式形式如下：
k
=
d
0
∗
2
0
+
d
1
∗
2
1
+
.
.
.
+
d
k
∗
2
k
k = d_0*2^0+d_1*2^1+...+d_k*2^k
k=d0∗20+d1∗21+...+dk∗2k
将数字k转为二进制数，即为在二进制下作数字拆分，与十进制数字拆分类似。
例：下面的代码为将数字k转为二进制并逆序输出
for(int a = k; a > 0; a /= 2)
cout << a%2;
拆分出的第0个数字为
d
0
d_0
d0，位权为
2
0
2^0
20，第1个数字为
d
1
d_1
d1，位权为
2
1
2^1
21…，第i个数字为
d
i
d_i
di，位权为
2
i
2^i
2i。
将k在二进制下作数字拆分，如果第i次拆分出的数字
d
i
d_i
di为0，则略过。如果第i次拆分出的数字
d
i
d_i
di不为0，则看i的值。
- 如果i为0，那么这一项为
2(0)
- 如果i为1，那么这一项为
2
- 如果i大于1，那么这一项为
2(s)，括号里的字符串s为将数字i转为2的幂次方表示的字符串，可以通过递归调用本函数得到。
- 递归出口：
【题解代码】
解法1：递归
#include<bits/stdc++.h>
using namespace std;
string solve(int k)
{
string s;
for(int a = k, i = 0; a > 0; a /= 2, i++)//其中一项为a%2*2^i
{
if(a%2 == 1)
{
if(i == 0)
s = "2(0)+" + s;//逆序构造字符串，需要将新得到的字符串接在s的前面
else if(i == 1)
s = "2+" + s;
else
s = "2(" + solve(i) + ")+" + s;
}
}
s.pop_back();//如果如上述方法构造字符串，最后末尾会多一个"+"，将这个"+"删掉。
return s;
}
int main()
{
int n;
cin >> n;
cout << solve(n);
return 0;
}
