【问题描述】：
4和7是两个幸运数字，我们定义，十进制表示中，每一位只有4和7两个数的正整数都是幸运数字，前几个幸运数字为：4，7，44，47，74，77，444，447······
输入：第一行一个数字T（T <= 1000）表示测试数据的组数，对于每组测试数据，输出一个数K（1 <= K <= 10(18) 10的18次幂）
输出：每组数据输出一行，第K个幸运数字
样例输入：
3
5
100
1000000000
样例输出：
74
744747
77477744774747744747444444447
【解题思路】
题目思路来源于看到百度知道中的一篇文章：acm 题目 ，在文中作者解题思路如下：
本来想广搜的，可是感觉不太好办，因为我不知道总共有多少个，然后什么记忆化什么的，又怕爆掉.....我就一直生活在自己的纠结当中.....
不过发现只有4和7就脑补了一个不错的算法。
我们发现4是第一个，7是第二个，44是第三个，47是第四个
不如将4看成0,7看成1，然后就得到二进制数了
4是0
7是1
可是44也变成0了，这就不太好了...于是想到在所有辛运数字前面加上7（也就是所有二进制前加一个1）这样我们就可以再列出一个表了：
4是10
7是11
44是100
47是101
74是110....哇真的是二进制诶.....所以直接将n像我那样拆分，就可以得到一个二进制串，再将二进制串变成十进制后减一即可。
最后附上代码（这算法比广搜帅气多了有木有....）
#include<cstdio> using namespace std; int main(){ int n,p,T; scanf("%d",&T); while(T--){ scanf("%d",&n); int ans=0; p=1; while(n>0){ //应该还是看得懂吧.... if(n%10==7) ans+=p; p<<=1; //这个表示二进制中的移位 n/=10; } ans+=p; printf("%d\n",ans-1); } return 0;}
【本文思路】
将上文作者的思路应用到此处，相当于先将输入的K+1转换成二进制，然后进行二进制编码的翻译工作
【注意事项】
因为K=10^9 ，int类型定义就够了
但是输出结果在第K个位置上数字大概会达到10^60 次方大小，超过了系统中int 等的赋值空间，所以在此使用字符串数组存储结果
【实验代码】
import java.util.Scanner;
public class KLuck2 {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
//System.out.println("please input test times");
int times=input.nextInt();
int[] posList=new int[times];
for(int i=0;i<times;i++){
posList[i]=input.nextInt();
}
kLuck(times,posList);
}
private static void kLuck(int times, int[] posList) {
// TODO Auto-generated method stub
if(times!=posList.length||times<=0||posList==null)
return;
for(int i=0;i<times;i++)
{
int pos=posList[i];
//n为输入的数值
char[] resultStr=new char[100];
int bit=kLuckAtPos(pos,resultStr);
// System.out.println(result);
//String s="";
// System.out.println();
printResult(resultStr,bit);
}
}
private static void printResult(char[] resultStr, int bit) {
// TODO Auto-generated method stub
if(bit==-1) return;
for(int i=bit-1;i>=0;i--)
System.out.print(resultStr[i]);
System.out.println();
}
private static int kLuckAtPos(int pos, char[] resultStr) {
// TODO Auto-generated method stub
if(pos<=0) return -1;
long ans=0;
int bit=0;
pos=pos+1;
//二进制编码等于位置+1 EG：44 对应位置 3 表示成二进制100
while(pos>0){
if((pos&0x1)>0) {
if((pos&0x3)==3&&pos>>2==0)
pos=pos>>1;
resultStr[bit]='7';
// ans=ans+(int)(7*Math.pow(10,bit));
}
else if((pos&0x0)==0){
if((pos&0x2)==2&&pos>>2==0)
pos=pos>>1;
resultStr[bit]='4';
}
bit=bit+1;
pos=pos>>1;
}
return bit;
}
}
运行结果：
3
5
100
1000000000
74
744747
77477744774747744747444444447