具有某些性质的第k个二进制数的查找算法

假设我们将考虑具有长度2n且n可能约为的二进制数1000。我们正在寻找具有以下属性的kth数字（k受限制10^9）：

• 的金额1's等于以下金额0's：#(1) = #(0)
• 这个数字的每个前缀都有到ATLEAST包含尽可能多0's的1's。这可能是更容易否定句，这是后明白：没有前缀，这将包含更多的1's比0's。

基本上就是这样。为了清楚起见，让我们做一些示例：n=2，k=2我们必须采用length的二进制数2n：

0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...

现在我们必须找到2nd满足这两个要求的编号。因此，我们看到的0011是第一个，0101第二个。如果我们更改k=3，则答案不存在，因为存在具有相同数量的相反位数的数字，但对于0110，则具有前缀，011因此数字不满足第二个约束，并且所有具有1最高有效位的数字都将是相同的。

那么到目前为止我做了什么来找到算法？

好吧，我的第一个想法是生成所有可能的位设置，并检查它是否具有这两个属性，但是生成它们全部都需要O(2^(2n))，这不是的选择n=1000。

另外，我意识到没有必要检查所有小于0011for n=2，000111forn=3等等的数字，以此类推...坦白地说，那些最高有效位的一半保持“不变”的数字，因为这些数字不可能满足#(1) = #(0)条件。使用它，我可以减少n一半，但并没有太大帮助。而不是永远2 *我有永远运行算法。它仍然很O(2^n)复杂，太大了。

对算法有任何想法吗？

结论

阅读Andy Jones帖子后，根据我的想法创建了本文。

首先，我不会发布我使用过的代码，因为以下内容来自Andy的Kasa 2009帖子中的第6点。您所要做的就是考虑nr我所说的k。取消Dyck单词算法的排名，将有助于我们更快地找到答案。但是它有一个瓶颈。

while (k >= C(n-i,j))

考虑到这一点n <= 1000，加泰罗尼亚语的数字甚至可能非常庞大C(999,999)。我们可以使用一些大数算法，但是另一方面，我想出了一点技巧来超越它并使用标准整数。

我们不希望加泰罗尼亚语数字大于多少才真正有多大k。因此，现在我们将创建加泰罗尼亚语数字，在n x n表中缓存部分和。

...                                     ...
5 |                              42     ...
4 |                        14    42     ...
3 |                   5    14    28     ...
2 |             2     5     9    14     ...
1 |       1     2     3     4     5     ...
0 | 1     1     1     1     1     1     ...
   ----------------------------------   ...
    0     1     2     3     4     5     ...

生成它很简单：

C(x,0) = 1
C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x
C(x,y) = C(x,y-1) where x == y

因此，我们只能看到以下内容：

C(x,y) = C(x,y-1) + C(x-1,y)  where y > 0 && y < x

会导致溢出。

让我们在此停止并提供定义。

k-flow-不是整数的实际溢出，而是信息的值C(x,y)大于k。

我的想法是在每次运行上述公式后检查是否C(x,y)大于k或大于总和-1。如果我们放了它（-1它会充当标记），那就k-flow已经发生了。我想很明显，如果将k-flow数字与任何正数求和，则仍然k-flowed特别是2个k-flowed数字之和k-flowed。

我们最后要证明的是，不可能产生真正的溢出。真正的溢出可能仅在我们总结a + b其中一个是非溢出的情况下才会发生，k-flowed但总的来说，它们才产生了真正的溢出。

当然不可能，因为最大值可以描述为a + b <= 2 * k <= 2*10^9 <= 2,147,483,647不等式中的最后一个值是带符号的int值。我还假设int具有32位，就像我的情况一样。