Lucky Number

http://blog.csdn.net/zengzhen_csdn/article/details/52450129

4和7是两个幸运数字，我们定义，十进制表示中，每一位只有4和7两个数的正整数都是幸运数字。前几个幸运数字是：4,7,44,47,74,77,444,447…

输入：
数字k

输出：
第k个幸运数

样例输入：
3
5
100
10000000

样例输出：
74
744747
44774447447477474444447

思路：
使用完全二叉树的思想，假设根节点为第0个数，值为-1；第1个数值为4，第2个数值为7，第3个数值为4，第4个数值为7，以此类推，即第奇数个数值为4，第偶数个数值为7。同时将其转为完全二叉树，如图所示：

于是第k个幸运数就是从位置为k的叶子结点向上遍历直到根节点的左或右子节点的路径。根据完全二叉树的性质，可以由子节点的位置求得其父节点的位置。若子节点是奇数位置n，则其父节点是(n-1)/2；若子节点是偶数位置，则其父节点是(n-2)/2。遍历过程中拼接字符串即可得到幸运数。

public void luckyNum(int n){ String res = ""; while(n > 0){ if((n & 0x01) == 1){ n = (n-1)/2; res = 4 + res; } else{ n = (n-2)/2; res = 7 + res; } } System.out.println(res); }
http://blog.csdn.net/u011824857/article/details/52494101
基本上都是用二进制的思想进行处理

1、将幸运数字的解空间，当做一个二叉树来处理

 2、一个j位长的幸运数字，可以看成是进行了j次选择，每次从4和7中选择一个作为幸运数字的一位，最终组成j+1层的二叉树

 3、为了方便计算，我们将选4记为0，将选7记为1

 4、求解的过程分两步：

 4.1、求解所在的层数（利用二叉树的特性来计算）

 4.2、求解是所在的层得几个节点（利用二叉树的性质来计算）

 5、将得到的选择转换成4和7，即0->4；1->7

1.     public static String getLuckNumber(int n){  
2.             //1、为方便处理将n装换成二进制的串  
3.             String str = Integer.toBinaryString(n);  
4.               
5.             //2、计算二叉树的层数层数  
6.             int level = str.length();  
7.             if(!str.contains("0")){  
8.                 level += 1;  
9.             }  
10.               
11.             //3、设定第n个是所在层的第k个，计算K  
12.             int m= n-((1<<(level-1)) -2);   
13.               
14.             //4、计算对应的二进制  
15.             //  （1）位数：就是所在层数减一，即level-1  
16.             //  （2）大小：树的同一层是从0开始记得，以第四层为例 000，001，010，011，100，101，110，111  
17.             //      而m是从1，开始记的，所以从零开始计的话，就是第m-1个节点，  
18.             //      第m-1个节点的值就是将m-1转成二进制，左面以0填充  
19.             String result = Integer.toBinaryString(m-1);  
20.             while(result.length()<level-1){  
21.                 result = "0"+result;  
22.             }  
23.               
24.             //5、将“0”换成“4”，“1”换成“7”,得到最终结果  
25.             result = result.replace("0", "4");  
26.             result = result.replace("1", "7");  
27.             return result;  
28.     } 

http://www.jianshu.com/p/47224ce04d2d
将4换成0，7换成1，那么
4, 7, 44, 47, 74, 77, 444, 447... 变成了
0, 1, 00, 01, 10, 11, 000, 001...对应的十进制是：
0, 1, 0, 1, 2, 3, 0, 1...看着没什么规律啊，不好处理，关键的问题在于00，01，000等都因为前边是0失去了本身的大小，那么如果我们在前面都加个1呢？
10, 11, 100, 101, 110, 111, 1000, 1001...变成十进制：
2, 3, 4, 5, 6, 7, 8, 9...
规律出来了。
我要求第K个数字，那么反向推不就得了。
先把K变成二进制（K+1的二进制），然后去掉最前面的1，然后将0替换为4，将1替换为7。答案就出来了。

http://m.blog.csdn.net/article/details?id=52443975

  while (cin.hasNextInt()) {

   count = cin.nextInt();
   int nArr[] = new int[count];
   for (int i = 0; i < count; i++) {
    nArr[i] = cin.nextInt();
   }
   for (int i = 0; i < count; i++) {
    StringBuilder resultBuilder = new StringBuilder();
    n = nArr[i];
    int length;
    for (int j = 2;; j++)
     if (n <= Math.pow(2, j) - 2) {
      length = j - 1;
      break;
     }
    while (length > 0) {
     length--;
     if (n > Math.pow(2, length + 1) - 2 + Math.pow(2, length)) {
      resultBuilder.append(7);
      n = n - (int) Math.pow(2, length + 1);
     } else {
      resultBuilder.append(4);
      n = n - (int) Math.pow(2, length);
     }
    }
    System.out.println(resultBuilder.toString());
   }

http://blog.tk-xiong.com/archives/956

代码如下： 注意一定是Long Long – 我调了20分钟，就是因为它。

C++

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

/* Author : xiong */ #include <stdio.h> typedef long long LL; void Lucky(LL n) {     if(n <= 0)return ;          LL Prev = (n-1)/2;     LL Now = n - Prev*2;     if(n == 1){         printf("4");         return ;     }     else if(n == 2){         printf("7");         return ;     }     else     {         if(Prev > 0)             Lucky(Prev);         if(Now > 0)             Lucky(Now);     } } int main() {     LL T;     scanf("%lld",&T);     while(T--)     {         LL n;         scanf("%lld",&n);         Lucky(n);         puts("");             } }

PS.幸运数我下来略微改动了一下，不过肯定可以AC的。

有人问思想，我来补充下。打表： 0 是 NULL

0	1	2	3	4	5	6	7	8	9	10
	4	7	44	47	74	77	444	447	474	477

我们可以看到

Lucky(3) 是 Lucky(1) + 4
Lucky(4) 是 Lucky(1) + 7

Lucky(5) 是 Lucky(2) + 4

Lycky(6) 是 Lucky(2) + 7

是不是和格雷码的 0 1  00 01 10 11 … 很像。

画个图哈

这样就很清楚了…

我要输出444 就输出 44 (Lucky(Prev)) 然后输出一个 4 (Lucky(Now))

我要输出 744 就输出一个 74 然后输出一个 4

好理解吧…

有网友简化了一下Lucky函数…这里贴一下：我还是稍微改了下…那些中间值不用也罢。

但是就是可能写上，清楚一些。 447 可以理解为 44是前一层， 7 是当前层。

C++

1 2 3 4 5 6 7 8 9 10 11 12

void Lucky(LL n) {     if(n <= 0)return ;          //先输出前面的数据     int Prev = (n-1)/2;     Lucky(Prev);          //然后输出当前层的数据     LL Now = n % 2;         Now == 0 ? printf("7") : printf("4"); }

然后根据网友的建议…再画一个二叉树的图…帮助理解：

按这个思路来：每一条路径就是一个结果…

这里网友提供了一种新方法：二进制方法 – 打表如下：

输入数据	二进制数据	处理分析	最终结果
1	1	不输出	NULL
2	10	0	4
3	11	1	7
4	100	00	44
5	101	01	47
6	110	10	74
7	111	11	77
8	1000	000	444
9	1001	001	447
10	1010	010	474

…后面就省略了-理论上完全可行的，略去了递归的层数。 代码如下：

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

void Lucky(LL n) {     //首先做 +1 处理     n+=1;     if(n <= 1)return ;     char Str[20];     int idx = 0;          //计算最后一位(这样是倒着计算的) - 注意当处理到1的时候表示结束     while(n > 1)     {         n&1 ? Str[idx++] = '7' : Str[idx++] = '4';         n = n>>1;     }          //所以输出的时候也倒着输出       for(int i = idx-1; i >= 0; i--    )     {         printf("%c",Str[i]);     } }