algorithm - 给定序列具有值的概率

Question

考虑一个具有按位操作数的有效字符串（即“xor”、“or”、“and”）以及“X”，其中 X 是来自 {0,1} 的整数。让我们考虑它们是 n 个“X”，那么它们是 2**n 个可能的字符串。我们需要找到值为“0”和值为“1”的字符串的数量。

例子 ：

考虑 4 个可能的“X&X”，只有 3 个的值为 0，只有一个的值为 1。

当字符串中的操作数不止一个位时，任何人都可以帮助我。

标签： algorithmdynamicprobabilityprobability-theory

Answer 1

您没有说，但我假设字符串的解释是通过从左到右关联（即0^1&0表示(0^1)&0）来完成的。我将使用|,&和^for or, and, xor。

设s为 n Xs 为 0t的任意字符串， 为 n Xs 为 1 的任意字符串。

然后，计算结果为 1 的具有 n+1 的字符串X看起来像以下之一：t|0, s|1, t|1, t&1, s^1, t^0。评估为 0 的是s|0, s&1, s&0, t&0, s^0, t^1。

固定一系列运算符，让 S(n) 是具有 nX的字符串的数量，使用给定的运算符计算为 0，T(n) 是计算为 1 的数字。假设你的第 i 个运算符给出的是 O(i)。然后，仅计算上一段中每个运算符的组合，您就有递归关系：

• S(1)=T(1)=1
• S(n+1), T(n+1) = S(n), S(n)+2T(n) 如果 O(i)=|
• S(n+1), T(n+1) = 2S(n)+T(n), T(n) 如果 O(i)=&
• S(n+1), T(n+1) = S(n)+T(n), S(n)+T(n) 如果 O(i)=^

这些递归关系很容易在 O(n) 动态程序中编码。