[算法-模拟] 4,7幸运数字

作者: Quasars | 来源:发表于2016-09-12 18:19 被阅读142次

[算法-模拟] 4,7幸运数字
2020 蓝桥杯大学 B 组模拟赛（五）
第六章更多监督训练
数学建模
Simulated Annealing (SA) Algorit
猪都能飞起来才算风口，AI是猪吗？
模数转换模块器的A/D转换器的工作原理
TSP问题—蚁群算法(ACO)
2018-11-14
数学建模最常用的数学算法

有一群矮人，他们的通信方式只有4和7. 他们的数字自然也只有4和7组成.例如,1 ~10他们表示为

现在要求给定一个地球人的数字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