※ 引述《Heyso (Heyso)》之铭言： : Catalan Number看到头痛还是很多问题 : 请教版上大大 : https://imgur.com/a/N9mxmPH : 例题47中，求的是n个变数可以有几种括号方法 : 前面的例题45中有规定每次只能结合两项 : 书上转换成RU的方式来解 : https://imgur.com/a/ukpRiNQ : 但小弟不太懂 : 1.为何只保留左括号和前3个变数 只去掉右刮弧，把左括弧当成运算子(operator)，就是 pre-order。 任意一棵二元树，将其树叶当成运算元(operand)，非树叶节点当运算子(operator)。 以 pre-order 排序，再去掉最後一个算元， 则上述由算子与算元组成的字串恰为 Dyck word，也就是等於合法的RU字串。 : 2.RRRUUU的组合中，不就相当於结合三项了吗 : 为何还是合法的? RRRUUU (((123 补上4 (((1234 将上面的字串看成pre-order，把左括弧当运算子 (((12)3)4) : 3.RRURUU(图片中第三个组合)若加入x4和右括号 : 可以写成((x1(x2x3x4)))和((x1(x2x3)x4))两种方法 : 一个是合法的，另一个不是 : 那为什麽还要省略掉第四个变数呢 为了凑出合法的RU字串，否则会多出一个U。 ----- 转换步骤整理如下: <A> monotonic lattice paths RURRUU <A to B> R → ( U → ) <B> Dyck word ( )(( ) ) <B to C> ( ______ ) ______ │ ↓ │ ↓ │ 左子树 │ 右子树 └──┬──┘ ↓ 根 ( )(( ) ) a 1 abc 2 c 3 b 4 <C> binary tree a / \ 1 b / \ c 4 / \ 2 3 <C to D> 父 ┌──┴──┐ ↓ ↓ ( 叶 叶 ) a bc c ba (1((2 3)4)) <D> expression (运算式) (1((2 3)4)) <D to E> 去掉右刮弧後 再去掉最後一个运算元 <C to E> 先pre order 再去掉最後一个树叶节点 <E> (1((2 3 或 a1bc2 3 <E to A> 左括弧 → R 运算元 → U 或 非树叶节点 → R 树叶节点 → U --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.248.67.227 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1530596995.A.5D9.html ※ 编辑: JKLee (211.72.73.139), 07/03/2018 18:40:16