2:2的幂次方表示
总时间限制:
-
1000ms
内存限制:
-
65536kB
描述
-
任何一个正整数都可以用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)
来源
-
NOIP1998复赛 普及组 第一题
-
-
这一题明显需要使用位运算加递归来实现,加好意味着有循环,独立的位置进行递归
-
#include <iostream>
using namespace std;
int GetBit(int n, int i)
{
return (n >> i) & 1;
}
void Exp(int n)
{
bool flag = true;
for(int i=15; i>=0; i--)
{
//只输出二进制非0的位数
if(GetBit(n, i))
{
if( !flag)
cout << "+";
else
flag = false;
if(i==0)//递归的终止条件 第0位
cout << "2(0)";
else if(i == 1) // 第一位
cout << "2";
else
{
cout << "2("; //第二位以上先输处"2(”
Exp(i); //压栈
cout << ")";
}
}
}
}
int main()
{
int n;
cin >> n;
Exp(n);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)