问题标签 [catalan]

我正在尝试创建 Prolog 规则以在 Prolog 中以列表形式枚举“二叉树”。我是 Prolog 的新手。

具有 0 个节点的树是一个空列表：

一棵有 1 个节点的树是：

具有 2 个节点的树有 2 种可能性：

等等。

这是我的规则：

对 0 和 1 的查询显然有效。对于 N=2，它会打印一种可能性，但在我输入分号以获得另一种可能性后会给出错误。N>2 的查询直接报错。错误总是一样的：

我在一些网站上读到了这个错误，但我不知道是什么导致了这个错误。

提前感谢您的帮助。

这个Wolfram链接谈到了一些关于“标记”二叉树的内容。那么是否也有所谓的“未标记”二叉树？对两者的简明解释会非常好。

我为什么要找这个？
我试图回答这个问题：

我们得到一组 n 个不同元素和一棵具有 n 个节点的未标记二叉树。我们可以通过多少种方式用给定的集合填充树，使其成为二叉搜索树？

现在，我知道给定 n 个节点的二叉树的数量是第 n 个加泰罗尼亚数，但现在我很困惑：这个公式适用于上述两种类型中的哪一种？

PS：对引号中的问题的一些帮助也会非常好:)

我正在为加泰罗尼亚数字编写程序。所以这是一个公式：

我决定使用公式的中间部分，因为其他部分对于我的知识来说太抽象了（也许我在数学课上睡得太多了）。实际上，我的程序可以正常工作n = 0;，但是如果我输入- 这里是繁荣 - 输出应该是。所以这是我的孩子：n = 5;n = 10;n = 15;29694845

如果有明显错误，请提前感谢您理解我。我是编程新手。

编号为 1、2、...、n 的引擎位于左侧的行中，当引擎离开右侧轨道时，需要重新排列（置换）引擎。位于支线轨道上的发动机可以留在原地，也可以沿着正确的轨道发送，但永远不能送回进入的轨道。例如，如果 n = 3，并且我们在左侧轨道上有编号为 1、2、3 的引擎，则 3 首先进入支线轨道。然后我们可以将 2 发送到支线，然后在其右侧，然后在途中发送 3，然后发送 1，获得新的订单 1,3,2。我们必须找到特定 n 的所有可能排列。

对于 n=1，答案 = 1；

对于 n=2 答案 = 2;

对于 n=3 答案 = 5；

没有发现任何普遍性。使用堆栈实现将非常有帮助。

但欢迎任何解决方案。

ps 这不是作业问题，因为我是一个自学成才的人。

我有使用二项式系数方法计算加泰罗尼亚语数的代码。

当我尝试计算 n 大于 510 的加泰罗尼亚数时，我得到一个“nan”结果。为什么会这样？我该如何解决？

我希望您对我（在 Python 中）实现的该算法的时间和空间复杂度提出意见，以计算算法的复杂度以打印 n 对括号的所有有效（即正确打开和关闭）组合（查看所有有效组合n 对括号的)

该算法很可能可以在时间和空间方面进行改进。请分享你的想法。

我正在使用此代码来计算加泰罗尼亚语数。它给了我正确的价值，直到 n=6 ，然后它给了我错误的价值。我使用计算器手动检查。例如：当 n=5 加泰罗尼亚数字是 42 时，这是正确的，但当 n=7 时，它给了我 6，这是完全错误的，因为答案应该是 429。我只是想不出什么是错的。有人能帮助我吗？

我正在寻找一种 Lisp 或伪代码中的算法来列出所有按加泰罗尼亚语关系排序的二叉树。

例如我想用输入'(a b c d)得到这个结果：(a (b (c d))) (a ((b c) d)) ((a b) (c d)) ((a (b c)) d) (((a b) c) d)

提前感谢您的帮助。

我编写了一个计算Catalan Numbers的递归函数。递归公式为。

我的代码：

现在，很明显递归深度是O(n)。我不确定这个算法的时间复杂度是多少。递归树有 O(n) 个节点，在任何节点（叶子除外）中我们进行两次调用。任何调用都是 O(1)，因为我们只检查字典中是否已经有结果，因此时间复杂度是 O(n)。

我的推理正确吗？

顺便说一句，是否可以选择编写以优于 O(n^2) 的时间复杂度运行的非递归算法？

谢谢！

我正在为家庭作业编写一个加泰罗尼亚语数字生成器，并且我正在 pytohon 中做一个递归程序。

该程序：

返回 5832，这是错误的答案，但是

给我 16796，这是正确的答案。

那么python不遵循PEMDAS吗？