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

Question

我们将特殊数字定义为仅包含 4 和 7 的数字。

让我们看例子:447 , 477 , 444 和 777 是特殊数字 而 407 不是。

我需要帮助来理解生成Nth 特殊号码的法律/规则 是什么。

我试过下面的代码，但没有用

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);

关于如何做的任何解决方案或想法？

Answer 1

为此我们可以使用二进制。将 4 称为 0，将 7 称为 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 <-这里

如图所示将它们映射到二进制文件，问题变得更容易了。 m 位特殊数字的个数为 2^m，请记住，2 的前 m 次幂之和为 2^(m+1)-1。如果我们有一个 3 位数字，那么我们通过将 1 位数字和 2 位数字相加来找到 k，剩下 2^0+2^1+2^2=2^3-1。排除 0 位数字，我们有 2^3-2 作为 k，这概括为 2^digits-2。为了找到位数，我们需要找出 n 以下有多少次 2 的幂。这只是 log2(n)，但我们必须将它排成一行并得到一个整数，所以我们取 floor(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 并且不希望出现负数，您可以简单地将数字保存在数组中而不是整数中并按顺序打印出来。