如何生成仅包含 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

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

4- 0      77-11

7- 1      444-000

44- 00      447-001

47- 01      474-010

74- 10      477- 011< -这里

将它们映射到如图所示的二进制文件，问题变得更容易。m 位特殊数字的数量将是 2^m，请记住，前 m 个 2 的幂之和是 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))。从这里开始，我们简单地使用 nk-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数字并且不希望出现负数，您可以简单地将数字保存在数组中而不是整数中，然后按顺序打印出来。