问题标签 [catalan]

我不是计算机程序员，但我的一个项目需要这个想法。我将解释我想要实现的目标：

这是两张图片图片 图片。我们可以编写代码来找出 两个孩子都是终端节点的节点数吗？如果是，那么我会花时间形成算法，或者我可能会尝试以其他方式实现它。

如果实现，我的问题的答案将是 3 (1+2)，基于上面的图片。

注意：1）这是完整的二叉树。2) 还有更多的树。3) 我正在使用 Python

我偶然发现了这个函数来计算加泰罗尼亚语数：

我的问题是如何sum获取值，例如 n=2：

sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))

catalan(2-1-0)如果我们n=1只为

我得到了具有分支因子 b 的大小为 N 的树的数量，并尝试在不使用单独的递归函数来生成嵌套 for 循环的数量的情况下生成加泰罗尼亚数。

到目前为止我已经尝试过了

对于 4 的大小和 2 的分支因子，我希望这个函数返回 14，但我收到的是 21。

提前致谢。

在研究catalan numbers时，我遇到的一些应用是：

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

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

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

有人可以解释一下。

我有以下代码，需要确定这个算法的运行时间。

由于递归内部的循环，我很难确定运行时间。我知道我需要将其转换为回归公式，然后对其进行分析，但我不知道该怎么做。

Leetcode上的标准Generate Parenthesis问题如下

在解决方案选项卡中，他们解释了我发现很难理解的闭包编号方法。

我对代码进行了试运行，甚至得到了正确的答案，但似乎无法理解它为什么起作用？这种方法背后的直觉是什么？

任何帮助将不胜感激！

我正在编写 Python 代码以使用此处给出的数学公式生成加泰罗尼亚数字：

C(0) = 1 和 C(n) = (2(2n - 1) / (n + 1)) * C(n - 1) 每个网站在这里。（https://rosettacode.org/wiki/Catalan_numbers）

但是，当我在 python 中将它作为函数编写时，它给了我错误的结果。

例如：对于 20 答案应该是 6564120420.0 而我的代码给了我 344373768。

这里：

有人可以帮我解决这个问题吗？

我如何才能有效地生成无限的加泰罗尼亚数字列表？我现在所拥有的工作相当快，但在我看来应该有更好的方法。

我尝试fix改用，但 lambda 不够懒惰，无法终止计算：

^{我意识到(++)并不理想}

这种更好的方法存在吗？可以使该功能足够懒惰吗？^{我知道，n th}有一个明确的公式，但我宁愿避免它。

总结一下，我只想检查最大堆栈深度是多少。

有人能帮我吗？

对于给定的 n 找到有效括号的有效组合的数量。我告诉他加泰罗尼亚数的直接公式（因为我之前遇到过这个问题）但他特别想要这个问题使用动态编程的解决方案，并想要带有测试用例解释的工作解决方案。我没有设法找到有效的解决方案。

例如：

n=1 有效面值=0

n=2 有效面值=1

现在我只想了解这个问题

我找到了一种解释，但没有得到它请您帮助我理解，或者您能否提供对以下逻辑的更详细的解释（这似乎是正确的）

你需要偶数个括号，如果 C(n) 用 2 * n 括号表示有效括号的数量，那么

C(0)=1 and for any n>0

C(n)=C(0) * C(n-1)+C(1) * C(n-2)+...+C(n-1) * C(0)=sum(i=0,n-1,C(i) * C(n-1-i))

因为您需要以 '(' 开头并查看带有 ')' 的右括号在哪里，如果它们之间有 2 * i 括号，那么这种情况的数量是C(i) * C(n-1-i).