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

概述我们将一个特殊数字定义为仅包含4和7的数字. 让我们看一些例子：447,477,444和777是特殊数字,而407则不是. 我需要帮助才能理解生成第N个特殊数字的法律/规则是什么. 我尝试了下面的代码,但它没有用 int x[2000];int k=0;void dfs( int a ) { if(k==1021) return; x[k++]=a; dfs(a*10+4 我们将一个特殊数字定义为仅包含4和7的数字.

让我们看一些例子：447,477,444和777是特殊数字,而407则不是.

我需要帮助才能理解生成第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并且不想要出现负数,你可以简单地将数字保存在数组而不是整数中并按顺序打印出来.

总结

以上是内存溢出为你收集整理的algorithm – 如何生成仅包含2种数字的第n个数字？全部内容，希望文章能够帮你解决algorithm – 如何生成仅包含2种数字的第n个数字？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。