algorithm – 如何生成仅包含2种数字的第n个数字？

int x[2000];
int k=0;

void dfs( int a ) {
  if(k==1021)
    return;
  x[k++]=a;
  dfs(a*10+4);
  dfs(a*10+7);
}

dfs(4);
dfs(7);

为此,我们可以使用二进制.将4s称为0,将7s称为1,因为7> 4.假设我们正在寻找第n个特殊号码.将k定义为具有第n个特殊数字的较少位数的特殊数字的数量.现在,我们看到如何使用二进制文件.假设我们知道第10个特殊数字有3位数,那个k = 6.我们正在寻找3位特殊数字列表中的10-6 =第4个数字.

4 – 0 77 – 11

7 – 1 444 – 000

44 – 00 447 – 001

47 – 01 474 – 010

74 – 10 477 – 011< -Here 如图所示将它们映射到二进制,问题变得更容易. m位特殊数的数量将是2 ^ m,并且记住两个的前m个幂的总和是2 ^(m 1)-1.如果我们有一个3位数字,那么我们通过将1位和2位数字相加得到k,留下我们2 ^ 0 2 ^ 1 2 ^ 2 = 2 ^ 3-1.排除0位数字,我们将2 ^ 3-2作为k,这推广到2 ^位-2.为了找到位数,我们需要找出两个低于n的幂.这只是log2(n),但我们必须将它排成一行并得到一个整数,所以我们采用下限(log2(n 1)).从这里开始,我们只使用n-k-1的二进制表示,然后使用按位函数提取每个数字并将数字添加到我们的答案中.

int nthspecialnum( int n )
{
    int digits = (int)(log2(n+1));
    int k = pow( 2,digits ) - 2;
    int binary = n - k - 1;
    int answer = 0;
    for( int i = 0; i < digits; i++ ) {
        bool is7 = ((binary >> i) % 2) == 1;
        answer += (is7 ? 7 : 4)*pow( 10,i );
    }
    return answer;
}

这些数字变得非常快,所以如果你正在寻找大n并且不想要出现负数,你可以简单地将数字保存在数组而不是整数中并按顺序打印出来.