问题标签 [catalan]

例如对于 N=3，我们可以通过将它们全部列出来轻松找到，但是当被要求提供任意 N 值时，我遇到了问题。

我需要在 n 个元素上找到许多不同的二叉搜索树。我知道，n 个不同元素上的二叉搜索树的数量是加泰罗尼亚数。但是如果数字可以重复呢？在二叉搜索树中，左子树的元素小于根，右子树的元素等于或大于根。

这是我的代码，用于计算 n 个元素上的许多不同的二叉搜索树。我通过模 123456789 计算这个数字，因为它可能非常大。我可以简单地改变它来解决我的问题吗？

假设我们将考虑具有长度2n并且n可能约为的二进制数1000。我们正在寻找具有以下属性的kth数字（k 受 限制）：10^9

• 金额1's等于金额0's可以描述如下的数量：#(1) = #(0)
• 这个数字的每个前缀必须至少0's包含1's. 否定句子后可能更容易理解，即：没有前缀可以包含1's超过0's。

基本上就是这样。因此，为了清楚起见，让我们举个例子： n=2，k=2 我们必须取长度的二进制数2n：

现在我们必须找到2nd满足这两个要求的数字。所以我们看到0011的是第一个，0101也是第二个。如果我们更改k=3，则答案不存在，因为存在具有相同数量的相反位的数字，但是对于0110，存在前缀011，因此数字不满足第二个约束，并且所有具有1最高有效位的数字都相同。

那么到目前为止我做了什么来找到算法？

好吧，我的第一个想法是生成所有可能的位设置，并检查它是否具有这两个属性，但生成它们都将采用O(2^(2n))这不是n=1000.

此外，我意识到没有必要检查所有小于0011for n=2、000111forn=3等的数字……坦率地说，那些最高有效位的一半仍然“未触及”的数字，因为这些数字不可能满足#(1) = #(0)条件。使用它我可以减少n一半，但它没有多大帮助。而不是 2 * forever 我有永远运行的算法。它仍然O(2^n)是复杂的，这太大了。

对算法有什么想法吗？

结论

这篇文章是我在阅读 Andy Jones 帖子后的想法而创建的。

首先，我不会发布我使用过的代码，因为它是来自 Andy 的帖子Kasa 2009的以下文档中的第 6 点。您所要做的就是nr按照我所描述的那样考虑k。Unranking Dyck words 算法，将帮助我们更快地找到答案。但是，它有一个瓶颈。

考虑到这一点n <= 1000，加泰罗尼亚语数可能相当大，甚至C(999,999). 我们可以使用一些大数算术，但另一方面我想出了一个小技巧来超越它并使用标准整数。

我们不想知道加泰罗尼亚数实际上有多大，只要它大于k. n x n所以现在我们将在表格中创建缓存部分和的加泰罗尼亚数字。

生成它非常简单：

所以我们只能看到这个：

可能导致溢出。

让我们停在这一点上并提供定义。

k-flow- 这不是整数的真正溢出，而是值C(x,y)大于的信息k。

我的想法是在每次运行上述公式后检查是否C(x,y)大于k或任何总和分量-1。如果是我们把-1它作为一个标记，那就k-flow已经发生了。我想很明显，如果k-flow数字与任何正数相加，它仍然是k-flowed特别是 2 个k-flowed数字的总和k-flowed。

最后我们要证明的是，不可能产生真正的溢出。真正的溢出只有在我们总结a + b它们中的哪一个时才会发生，k-flowed但它们总和产生了真正的溢出。

当然这是不可能的，因为最大值可以描述为a + b <= 2 * k <= 2*10^9 <= 2,147,483,647这个不等式中的最后一个值是带符号的 int 值。我还假设 int 有 32 位，就像我的情况一样。

我在计算如下所示程序的时间复杂度时遇到了麻烦。这是一个生成有效括号的简单程序，例如“（（（）））”“（（）（））”等。但是，我真的不知道如何估计这类问题的时间复杂度。

如果您能在这里分享一些您认为有用的技术，我们将不胜感激。如果您可以分析我作为示例链接的程序，那将是最好的:)

我的目标 ：

1. 估计非平凡程序的时间复杂度。通常是一个有一些修剪的递归程序。

2. 我正在寻找一个快速估计的解决方案，而不是一个严格的数学证明。

先感谢您。

有问题的代码：

加泰罗尼亚数满足递归

当然，加泰罗尼亚数具有涉及二项式系数的封闭形式表达式。我们也可以单独用 C_{n-1} 来表示 C_n。我想知道的是如何在 SML 或 Haskell 等函数式语言中实现这种卷积。

http://www.cstutoringcenter.com/problems/problems.php?id=103

不想点的人，基本上就是说有个垫脚石，“-”和士兵“#”，士兵只能向右移动。如果士兵在另一个士兵后面，他必须等待士兵先移动。结束条件是所有士兵都到达终点。

2 名士兵在 5 个垫脚石上移动的方式数。

我使用广度优先搜索，有 5 个石头，它在几秒钟内运行，但有 10 个石头，它需要几个小时，时间随着深度呈指数增长。我该如何处理？

我的代码：

状态.java

士兵.java

TestSoldiers.java

我怎样才能做到这一点，以便我只考虑每个状态一次，同时保持结束方式总数的完整性（在 TestSoldiers.java 中计数）？

对于那些想要修改参数的人来说，它是新的 State(n,k)，其中 n 是石头的数量，k 是士兵的数量。

根据 wiki 的 wiki catalan 定义，我看到以下表达式：

我可以理解前两个表达，但对第三个表达真的很困惑。pi 符号代表乘法。该表达式是否表示以下代码：

我的代码如下

}

我得到的结果是完全错误的

有人帮我吗？

我想列出所有可能的二叉搜索树。我知道该号码将是加泰罗尼亚语号码。但我也想列出它们。

假设我为二叉搜索树的每个位置分配字母，如下所示

然后想要列出所有可能的具有 N 个节点的树。如果 N 为 1，那么唯一可能的树是

如果 N 为 2，那么可能的树是

如果 N 为 3，则可能的树是

如果 N 为 4，则可能的树是

有谁知道列出所有可能的树的好算法？

给定 n，有多少个结构唯一的 BST（二叉搜索树）存储值 1...n？

例如，给定 n = 3，总共有 5 个唯一的 BST。

我有这个解决方案：

因为这个答案是很久以前给出的，无法触及这个'dragonmigo'家伙。该解决方案被接受，我的问题是：

在评论中， trees[0] 指的是案例1。(0+1 = 1)

如果是这样，则 trees[n-1] 应该引用案例1...n而不是案例2...n。(n-1+1=n)

我的想法错了吗？

ps 我知道这实际上是一个加泰罗尼亚数字，并且我知道使用演绎公式解决它的算法。

我写了一些代码来计算第 N 个加泰罗尼亚语数。但是，当 N=20 及以后，它不会返回正确的结果。N<20 时的结果是正确的，所以我不确定哪里出了问题。

因此，当 N=20 时，它应该返回 6564120420，但它为我返回 2269153124。

有人可以指出我正确的方向吗？