我要计算不包含两个连续的1或3个连续的零的位字符串的数量
但不是两者都
我找到了一种算法，该算法由两个连续的1或3个连续的零组成，但是由于要排除它，所以未能找到它们之间的交集。
例如，我的输入为4。我需要查找所有没有3个连续0或2个连续1的4位长度序列。因此答案将是5：0010、0100、0101、1001和1010
有任何想法吗？
谢谢..
最佳答案
您可以使用以下方法：
递归计算序列数。
要知道子序列的数量，我们需要知道子序列之前的两位。
如果前一位是1...，则子序列必须以0开始。
如果前两个位是00...，则子序列必须以1开始。
如果先前的位与这些模式中的任何一个都不匹配，则子序列可以以0或1开头。
其余的应该从程序中清除：
public class BitSequences {
public static void main(String[] args) {
for (int i = 0; i <= 64; ++i) {
System.out.println(i + " " + bitSequences(i));
}
}
public static long bitSequences(int length) {
return bitSequences(length, Bit.NONE, Bit.NONE);
}
public static long bitSequences(int length, Bit prePreBit, Bit preBit) {
if (length <= 0) {
return 1;
} else if (preBit == Bit.ONE) {
return bitSequences(length - 1, preBit, Bit.ZERO);
} else if (prePreBit == Bit.ZERO && prePreBit == Bit.ZERO) {
return bitSequences(length - 1, preBit, Bit.ONE);
}
return bitSequences(length - 1, preBit, Bit.ONE)
+ bitSequences(length - 1, preBit, Bit.ZERO);
}
enum Bit {
ZERO,
ONE,
NONE
}
}
通过使用动态编程可以改善程序，但是在您的情况下可能并不重要。
length = 64的计算在一秒钟内完成。结果：有109'870'576（约228个）长度为64的位串，其中没有11或000。关于java - p的交点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42874981/