【一个比较经典的算法题目】
题目链接：
http://lx.lanqiao.org/problem.page?gpid=T235
http://noi.openjudge.cn/ch0202/8758/
问题描述
任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。
将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0
现在约定幂次用括号来表示，即a^b表示为a（b）
此时，137可表示为：2（7）+2（3）+2（0）
进一步：7=2^2+2+2^0 （2^1用2表示）
3=2+2^0
所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：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）
将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0
现在约定幂次用括号来表示，即a^b表示为a（b）
此时，137可表示为：2（7）+2（3）+2（0）
进一步：7=2^2+2+2^0 （2^1用2表示）
3=2+2^0
所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：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）
输入格式
正整数（1<=n<=20000）
输出格式
符合约定的n的0，2表示（在表示中不能有空格）
样例输入
137
样例输出
2(2(2)+2+2(0))+2(2+2(0))+2(0)
样例输入
1315
样例输出
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
提示
用递归实现会比较简单，可以一边递归一边输出
提示
用递归实现会比较简单，可以一边递归一边输出
分析：
本题可以参考一个算法:递归输出某十进制数的二进制表示的算法。（主要是在递归回溯的时候才输出，而非计算出来就输出。）
本着从易到难的原则，可以考虑先实现将137表示为：2（7）+2（3）+2（0）的程序。
关于加号的输出：可以考虑判断当前项是否二进制序列的最高位（传入下一层的数是0）。是最高位则当前项左侧不输出“+”，否则在当前项左侧输出“+”.
关于把指数也转变为0和2的序列：在输出每一项时判断指数是否超过1，超过则先输出“2(”，然后把该指数与0传入递归函数，递归显示该指数的表示。然后在输出后半边括号。
嗯可以先看看递归输出一个整数的二进制序列：
程序0：
#include <stdio.h> void fun(int n) {
int t; if(n==0) return; else { t=n%2; fun(n/2); printf("%d",t); } } int main() { fun(5); return 0; }
程序一：实现将137表示为：2（7）+2（3）+2（0）的程序.
1 #include <stdio.h> 2 void toBinary(int n,int x); 3 int main() 4 { 5 int n; 6 freopen("out1.txt","w",stdout); 7 n=1; 8 while(n<=255) 9 { 10 //scanf("%d",&n); 11 printf("%d---->",n); 12 toBinary(n,0); 13 printf("\n"); 14 n++; 15 } 16 17 return 0; 18 } 19 void toBinary(int n,int x) 20 { 21 int t; 22 if(n==0) 23 return; 24 else 25 { 26 t=n%2; 27 toBinary(n/2,x+1); 28 if(t) 29 { 30 if(x==1) 31 { 32 if(n/2==0) 33 printf("2"); 34 else printf("+2"); 35 } 36 else 37 { 38 if(n/2==0) 39 printf("2(%d)",x); 40 else printf("+2(%d)",x); 41 } 42 } 43 } 44 }
程序二：完整程序的实现。
1 #include <stdio.h> 2 void toBinary(int n,int x); 3 int main() 4 { 5 int n; 6 /*scanf("%d",&n); 7 toBinary(n,0);*/ 8 9 freopen("out2.txt","w",stdout); 10 n=1; 11 while(n<=255) 12 { 13 //scanf("%d",&n); 14 printf("%d---->",n); 15 toBinary(n,0); 16 printf("\n"); 17 n++; 18 } 19 20 return 0; 21 } 22 void toBinary(int n,int x) 23 { 24 int t; 25 if(n==0) 26 return; 27 else 28 { 29 t=n%2; 30 toBinary(n/2,x+1); 31 if(t) 32 { 33 if(x==1) 34 { 35 if(n/2==0) 36 printf("2"); 37 else printf("+2"); 38 } 39 else 40 { 41 if(n/2==0) 42 { 43 //printf("2(%d)",x); 44 if(x==0) printf("2(0)"); 45 else 46 { 47 printf("2("); 48 toBinary(x,0); 49 printf(")"); 50 } 51 } 52 else 53 { 54 //printf("+2(%d)",x); 55 if(x==0) printf("+2(0)"); 56 else 57 { 58 printf("+2("); 59 toBinary(x,0); 60 printf(")"); 61 } 62 } 63 } 64 } 65 } 66 }
更新：上述代码的if逻辑可以简化。
1 #include <stdio.h> 2 void toBinary(int n,int x); 3 int main() 4 { 5 int n; 6 /*scanf("%d",&n); 7 toBinary(n,0);*/ 8 9 freopen("out2.txt","w",stdout); 10 n=1; 11 while(n<=255) 12 { 13 //scanf("%d",&n); 14 printf("%d---->",n); 15 toBinary(n,0); 16 printf("\n"); 17 n++; 18 } 19 20 return 0; 21 } 22 void toBinary(int n,int x) 23 { 24 int t; 25 if(n==0) 26 return; 27 else 28 { 29 t=n%2; 30 toBinary(n/2,x+1); 31 if(t) 32 { 33 if(x==1) 34 { 35 if(n/2==0) 36 printf("2"); 37 else printf("+2"); 38 } 39 else 40 { 41 if(n/2!=0)printf("+"); 42 43 if(x==0) printf("2(0)"); 44 else 45 { 46 printf("2("); 47 toBinary(x,0); 48 printf(")"); 49 } 50 } 51 } 52 } 53 }
