A26637. 2的幂次方表示
题目描述
2的幂次方表示
题目描述
任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20
同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)
进一步：7=22+2+20（21用2表示）
3=2+20
所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=210+28+25+2+1
所以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表示（在表示中不能有空格）。
输入样例
137输出样例
2(2(2)+2+2(0))+2(2+2(0))+2(0)参考答案
#include<bits/stdc++.h>
using namespace std;
string solve(int k)
{
string s;
for(int a = k, i = 0; a > 0; a /= 2, i++) if(a%2 == 1)//其中一项为a%2*2^i
{
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;
}答案解析
#include<bits/stdc++.h>
using namespace std;
void solve(int k)//k的第0位是原数字n的第几位
{
if(k == 0)
return;
int i = 0, v = 1;//i：k最低位1是二进制下的第几位 v：k最低位1的位权
//int v = k & -k, i = log2(v);//v和i也可以不需要下面的循环，直接求出
for(int a = k; a > 0; a /= 2)
{
if(a%2 == 1)
break;
i++;
v *= 2;
}
solve(k-v);
if(k > v)//如果k>v，那么接下来要输出的就不是第1项，需要先输出加好
cout << '+';
if(i == 0)
cout << "2(0)";
else if(i == 1)
cout << "2";
else
{
cout << "2(";
solve(i);
cout << ")";
}
}
int main()
{
int n;
cin >> n;
solve(n);
return 0;
}