n 个变量都是布尔类型的,支持的运算有与或和小括号(运算优先级),能生成多少种运算表达式?

比如有 a b c 3 个变量,则有

a and c or b

(a or b) and c

.
.
.

这种表达式怎么用程序枚举出来?

Click to rate this post!
[Total: 0 Average: 0]

相关文章

15 thoughts on “n 个变量都是布尔类型的,支持的运算有与或和小括号(运算优先级),能生成多少种运算表达式?

  1. 你没有限定条件,那就不可能枚举。
    先写一个

    for i in itertools.count():
       print(“a and “*i+”a”)

  2. @zhoudaiyu 什么叫 “多少种”
    你看看我的代码,只有一个变量,一秒生成几万种运算表达式

  3. abc 能否重复出现?
    能重复的话,最多重复的次数是多少?
    可以无限次重复的话,自然就是无限解,呃,结果应该还是有限的,只是写法无限,

  4. 有个暴力的想法,变量和符号先爆搜定下来,然后再爆搜放括号,然后再判断合法性

  5. 已经一年多没碰 OJ 了…花了 10 分钟想了个思路:

    思路:这个问题问的是:“有多少种语法树”。

    首先明确一下题目:有 n 个变量。我们简化一下题目,把变量统一换成 i 。
    这样,求出的最终结果只需要乘上 n 个元素的全排列数量 A(n,n),就可以得到最终的答案。

    然后我们对语法建模。这个文法可以用经典的表达式文法稍作变形得到:
    E -> E op T | T
    T -> i | (E op E) // 这里假设不能有(((i)))这种套娃,否则就无限种了
    op -> 与 | 或

    如果没学过文法,可以用直觉理解:
    如果一个式子是“(i & i) | i”,
    那么这个式子的语法树的推导为:
    E => E op T => T op T => (E op E) op i => (i op i) op i => (i & i) | i 。
    每一次我把一个符号扩展的时候,就是建立一个子树的动作。

    另外,又因为这个文法不是二义文法,所以得到的答案不会重复。

    好了,现在就对这个文法的建模完毕了。
    同时注意,op 可以不展开,只需要在最后呈上 2^(运算符个数)就行了。

    >>> 我们的任务转换为:求满足条件的语法树的种类。条件:语法树的叶子节点有 N 个 i 。

    ================= 分割线

    好,现在一个笨办法就是,用递归,在每个节点,都对所有可能的子树做尝试。但不能无休止的尝试,应该剪枝。剪枝的方法就是:如果当前的 i 的数量大于 N,那么就 return (剪枝)。

    然而,这个办法时间复杂度没有经过优化。

    我们可以想到第二种方法:
    对于每一个非终结符( E, T ),维护一个表 table:key=(非终结符, i 的数量),value=子树种类。
    例子:table[(‘E’, 5)]=10 的意思是,以 E 为根节点,满足“有 5 个 i”的语法树的数量为 10.

    现在就可以通过 [递推] 来解决了。

    ===

    由于思考时间短暂,文法等推理如果有错误请谅解。(大体的思路是可行的)

  6. 一种思路 口 代表变量 O 代表运算符
    把 这个表达式的 口 O 口 O 口 括号可能的情况全部输出来 然后再做排列组合的填空会简单很多

  7. 不就是一个排序组合嘛, 比如 3 个变量 a,b,c or , and ,(,) 就这几个数排列组合打印下, 然后把出来的表达式用 编译器编译下 去掉编译错误表达式,留下的都是正确的。

  8. @zhoudaiyu 你看,这不是就限制嘛
    对,我上面搁着明白装糊涂呢
    符合交换律的算不算? a and b 和 b and a 是不是一样的?
    无效括号算不算?(a and b) or c 和 a and b or c 是不是一样的?

  9. 首先排列 n 变量进行排列
    n!
    然后在缝隙中插入 或与
    n! * 2^(n-1)

    然后在数字后面插入 “)”

    * 第 n 个数字后面可以插入最多 (n-1)个 “)” 这里 “(变量)” 这种形式视为无效
    *第 n 个数字可能具有的括号排列 2^(n-1)
    等价为 n-1 个”(” 可能存在可能不存在的队列
    *n 个数字可能具有的括号排列 2^(2-1) *2^(3-1) *…* 2^(n-2) * 2^(n-1)

    然后得到 {n! * 2^(n-1)}*{2^(2-1) *2^(3-1) *…* 2^(n-2) * 2^(n-1)}

发表回复

您的电子邮箱地址不会被公开。