Openjudge 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复赛 普及组 第一题

参考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);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注