p 的交集

Question

我想统计 Not 由两个连续的 1 组成的位串的个数 OR 3 个连续的 0

但不是两者都

我找到了一个由两个连续的或 3 个连续的零组成的算法，但我没有找到它们之间的交集，因为我想排除它..

比如我的输入是4，我需要找出所有不是三个连续0或者两个连续1的4位长度的序列。所以答案是 5：0010、0100、0101、1001 和 1010

有什么想法吗？谢谢..

Answer 1

您可以使用以下方法：

递归计算序列数。
要知道子序列的个数，我们需要知道子序列前的两位。
如果前一位是 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（大约2²⁸）个长度为64的位串，其中没有11或000。

p 的交集

intersection of p

java

permutation

bit