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复赛 普及组 第一题
参考http://blog.csdn.net/u011954296/article/details/51029600写成代码，不胜感激！
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 48 49 | #include<cstdio> #include<cstring> using namespace std; int n; //print函数里包含了两层逻辑，1是把输入的n用递归的方式化成二进制数传递下去，2是要把2的幂次方位再次调用该函数 void print(int n,int t){//n为该十进制数,t为递归层数 if(n==1){//当n==1时，即化成的二进制数为1，会放在整个式子的最前面输出，所以前面不能有加号 switch(t){ case 2: printf("2(2)"); break; case 1: printf("2"); break; case 0: printf("2(0)"); break; default://里面不是0，1，2就要将递归层数（即二的幂次方的指数）重新递归 printf("2("); print(t,0); printf(")"); break; } return; } print(n/2,t+1);//遵循10进制转2进制向下递归 if(n%2==1){ switch(t){ case 2: printf("+2(2)"); break; case 1: printf("+2"); break; case 0: printf("+2(0)"); break; default: printf("+2("); print(t,0); printf(")"); break; } } } int main(){ scanf("%d",&n); print(n,0); } |
20180730洛谷P1010更新：
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 | #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<string> #include<vector> #include<queue> #include<map> #include<functional> using namespace std; string f[20005]; //2^pow inline int getBit(int num,int pos) { return (num >> pos) & 1; } string cal(int num) { if (f[num] != "")return f[num]; string s = "2("; bool flag = false; for (int i = 15; i >= 0; i--) { if (getBit(num, i)) { if (!flag) flag = true; else s += "+"; s += cal(i); } } return f[num] = s+")"; } int main() { f[0] = "2(0)"; f[1] = "2"; int n; cin >> n; string s = cal(n); cout <<s.substr(2,s.length()-3); } |