gpt4 book ai didi

math - Number of valid parenthesis 加泰罗尼亚数字解释

转载 作者:行者123 更新时间:2023-12-05 02:13:05 25 4
gpt4 key购买 nike

在研究catalan numbers时,我遇到的一些应用程序是:

  1. 没有使用 n 个节点的可能的二叉搜索树。
  2. 没有任何方法可以使用圆上的 2*n 个点绘制不相交的弦。
  3. 没有办法安排 n 对括号。

虽然我理解前两个问题,即加泰罗尼亚数字如何适合他们的解决方案,但我无法理解它们如何适合第三个问题。

在互联网上找不到任何其他有用的资源来解释HOW 部分。每个人都说这是解决方案。

谁能解释一下。

最佳答案

由于其他人似乎不同意我认为这个问题是题外话,所以我现在决定它是题外话并提供和回答。

维基百科确实对“排列 n 对括号的方法的数量”(this link 中的第二个要点)感到困惑。部分混淆是括号字符串的顺序与顺序不匹配二叉树,你确实理解,或者与许多其他示例一起使用。

这是一种将正确匹配的 n 对括号的字符串转换为具有 n 个内部节点的二叉树的方法。考虑最左边的括号,这将是一个左括号,连同它匹配的右括号。将字符串变成二叉树的一个节点。当前考虑的括号内部的子字符串成为该节点的左子节点,之后(右侧)的子字符串-考虑右括号成为右 child 。一个或两个子字符串可能为空,当前考虑的括号被简单地删除。如果任一子字符串不为空,则递归地继续此过程,直到删除所有括号。

这里有两个例子。让我们从字符串 ((())) 开始。我们从

开始

enter image description here

考虑的括号是最外面的。这变成了

enter image description here

(我没有费心画外部叶节点)然后

enter image description here

然后

enter image description here

这是维基百科最左边的二叉树,有 3 个内部节点。

现在让我们做另一个字符串,(())()。我们从

开始

enter image description here

同样,被考虑的括号是最外面的。这转换为

enter image description here

现在考虑的括号是前两个,而不是最外面的。这变成了

enter image description here

最后变成

enter image description here

这是维基百科列表中的第二个二叉树。

我希望你现在明白了。这是正确配对的 3 对括号的所有五个可能字符串的列表,后面是维基百科的二叉树列表。这些列表现在相互对应。

    ((()))       (()())        (())()       ()(())       ()()()

enter image description here

关于math - Number of valid parenthesis 加泰罗尼亚数字解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55143409/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com