2的次幂表示【递归算法训练】

浏览数：41 / 时间：2015年06月08日

【一个比较经典的算法题目】

题目链接：http://lx.lanqiao.org/problem.page?gpid=T235

问题描述

　　任何一个正整数都可以用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）

输入格式

　　正整数（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传入递归函数，递归显示该指数的表示。然后在输出后半边括号。

程序一：实现将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(",x);
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(",x);
59                         toBinary(x,0);
60                         printf(")");
61                     }
62                 }
63             }
64         }
65     }
66 }