这更像是一个难题而不是编码问题.我需要找到可以生成满足某些约束的二进制数.输入是
(integer) Len - Number of digits in the binary number
(integer) x
(integer) y
二进制数必须是这样的,从二进制数中取任何x个相邻数字应该至少包含y 1.
例如 -
Len = 6,x = 3,y = 2
0 1 1 0 1 1 - 长度为6,从中获取任意3个相邻数字,将有2个数字
我在面试中向我提出了这个C#编码问题,我无法弄清楚任何算法来解决这个问题.不寻找代码(尽管欢迎它),任何形式的帮助,指针都很受欢迎
以 LEN = 6、X = 3 和 Y = 2 为例...
为 X 位构建详尽的位模式生成器。一个简单的二进制计数器就可以做到这一点。例如，如果 X = 3，则从 0 到 7 的计数器将生成长度为 3 的所有可能的位模式。
这些模式是：
000
001
010
011
100
101
110
111
在构建模式时验证邻接要求。拒绝任何不合格的模式。基本上，这可以归结为拒绝包含少于 2 个“1”位 (Y = 2) 的任何模式。该列表精简为：
011
101
110
111
对于修剪列表的每个成员，添加“1”位并重新测试前 X 位。如果新模式通过了邻接测试，则保留新模式。对“0”位执行相同操作。例如，此步骤进行如下：
1011 <== Keep
1101 <== Keep
1110 <== Keep
1111 <== Keep
0011 <== Reject
0101 <== Reject
0110 <== Keep
0111 <== Keep
其中留下：
1011
1101
1110
1111
0110
0111
现在重复此过程，直到剪枝集为空或成员长度变为 LEN 位长。最后剩下的唯一模式是：
111011
111101
111110
111111
110110
110111
101101
101110
101111
011011
011101
011110
011111
数一数就完成了。
请注意，您只需在每次迭代中测试前 X 位，因为所有后续模式都已在前面的步骤中进行了验证。