有一群矮人，他们的通信方式只有4和7. 他们的数字自然也只有4和7组成.例如,1 ~10他们表示为
1 4
2 7
3 44
4 47
5 74
6 77
7 444
8 447
9 474
10 477
...
现在要求给定一个地球人的数字N（1<= N <= 10 ^ 18）,求矮人族中对应的表达.
如，
输入 5
输出 74
输入 100000000000
输出 477747447444477747747774744444444447
解法
思路1. 二叉树广度优先遍历， 只针对小规模数字.
解法如下：
1 #include <iostream>
2 #include <cstdio>
3 #include <string>
4 #include <queue>
5
6 using namespace std;
7
8 queue<string> q;
9 string ss;
10 unsigned long long N;//1 ~ 10 ^ 18
11
12 void next()
13 {
14 unsigned long long Ptime = 1;
15 unsigned long long pi;
16 while(N){
17 pi = Ptime;
18 while(pi){
19 string tmp = q.front();
20 q.pop();
21 pi--;
22
23 tmp += "4";
24 q.push(tmp);
25 N--;
26
27 if(0 == N){
28 cout << tmp << endl;
29 return;
30 }
31
32 tmp[tmp.size()-1] = '7';
33 q.push(tmp);
34 N--;
35 if(0 == N){
36 cout << tmp << endl;
37 return;
38 }
39 };
40 Ptime = Ptime << 1;
41 }
42 }
43
44 int main()
45 {
46 scanf("%llu", &N);
47 q.push(string(""));//null-string
48 next();
49 return 0;
50 }
在这个思路的启发下，有思路二.
- 思路2，（真正的解法）.观察可得出，在一定长度下，4对应着二进制0,7对应着二进制1，只需求得每次相同长度下的第一个数，（通过求二叉树前k层节点总数可求得），N减去该数字，然后按位进行计算，
0对应4,1对应7。
1 #include <iostream>
2 #include <cstdio>
3 #include <string>
4
5 unsigned long long N;
6 void next()
7 {
8 unsigned long long sum = 0;
9 unsigned long long base = 1;
10 int bitsum = 0;
11 while(sum < N){
12 base *= 2;
13 sum += base;
14 bitsum++;
15 };
16 sum -= base;
17
18 //printf("%llu\n", sum + 1);
19 N -= (sum + 1);
20 std::string ss(bitsum, '4');
21 int biti = 0;
22 //printf(" N-sum %llu\n", N);
23 /*printf("====\n");
24 while(N){
25 printf("%d",(N & 1) ? 1 : 0);
26 N = N >> 1;
27 }
28 printf("\n");
29 */
30 while(N)
31 {
32 if(N & 1){
33 ss[ss.size() - 1 - biti] = '7';
34 }
35 N = N >> 1;
36 biti++;
37 }
38 std::cout << ss << std::endl;
39 }
40
41
42
43 int main()
44 {
45 scanf("%llu", &N);
46 next();
47 return 0;
48 }
运行结果，
work@vm1:~$ ./test47（第一种思路）
100
744747
work@vm1:~$ ./test472（第二种思路）
100
744747
work@vm1:~$ ./test47
100000000
^C(超时)
work@vm1:~$ ./test472(大规模情况下不超时)
100000000000
477747447444477747747774744444444447
