Вероятность того, что данная последовательность имеет значение

Question

Рассмотрим допустимую строку с побитовыми операндами (то есть «xor», «or», «and»), а также «X», где X - целое число из {0,1}. Давайте рассмотрим, что это n чисел «X», тогда их 2 ** n возможных строк. Нам нужно найти количество строк, которые имеют значение как «0» и значение как «1».

Пример :

Рассмотрим "X & X" из 4 возможных, только 3 имеют значение 0, и только один имеет значение 1.

Может кто-нибудь мне помочь, если их более чем один битовый операнд в строке.

Answer 1

Вы не говорите, но я предполагаю, что интерпретация строк выполняется путем связывания слева направо (то есть 0^1&0 означает (0^1)&0). Я буду использовать |, & и ^ для или, и xor.

Пусть s будет произвольной строкой с n X s, который оценивается в 0, и t быть произвольной строкой с n X s, которая оценивается в 1.

Тогда строки с n + 1 X s, которые оцениваются в 1, выглядят как одна из: 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) будет число строк с n X s, которые оцениваются в 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) Dynami c .