问题标签 [catalan]

在过去的几个小时里，我一直试图解决这个问题，但我就是不明白。我知道必须有一种数学计算来计算它，但我不知道如何准确计算它。我知道这段代码没有意义，因为我完全迷路了，我将不胜感激任何提示或帮助，以帮助我更接近解决方案。

我问了我的教授，他告诉我一个提示，它类似于使用字母表的排列/组合，例如 26^3 用于 3 种不同的组合，但这对我没有多大帮助。

我知道的：

1. 字符串中给出的输入有 796 个字符，我必须找到 796 个字符可以采用平衡括号形式的所有可能方式。

2. 由于它必须以 '(' 开头并以 ')' 结尾，因此每种情况必须有 2 个括号。所以它可以是'()()(xc)(cvs)'。因此，这意味着数学计算必须涉及每个 char(s) 2*(something)，因为它必须是平衡的。

3. 我需要使用 rest(%) 运算符递归地查找每个案例，但是当我接受 a charin 而不是a 时，我该怎么做int？

我不知道的是：

1. 我将如何分析每个案例？如果没有简单的公式来计算输入，这不会花费很长时间或大量代码吗？

2. 我需要很多 -if语句或递归吗？

问题：

令 Σ = {), (}。令 L ⊆ Σ* 是正确平衡括号的字符串集合。例如，(())() 在 L 中，而 (()))( 不在 L 中。形式上， L 递归定义如下。

ε ∈ L

串 x ≠ ε 在 L 当且仅当 x 的形式为 (y)z，其中 y 和 z 在 L 中。

n 是 0 到 999 之间的特定 3 位数字。

计算 f(n) mod 997

您可能会发现一些有用的事实：如果 n1，n2 是 N（自然数）的成员，那么，

(n1 x n2) mod 997 和 (n1 + n2) mod 997

n = 796（这对我来说是特定的，在这种情况下这将是给定的输入）

所以我必须“计算 f(796) mod 997 = ?” 使用程序。在这种情况下，我将简单地使用 java 来回答这个问题。

代码：

我想知道是否有人可以回答我，这是在下一个问题的回溯解决方案中生成的结果数量：

给定 n 对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定 n = 3，解集是：

“((()))”、“(()())”、“(())()”、“()(())”、“()()()”

stackoverflow中有一篇相关的帖子：Generate balance parentheses in java

我怀疑是否有一个公式可以给我计算之前可以生成的有效括号的数量。例如：
- f(n):
- f(1) = 1
- f(2) = 2
- f(3) = 5
等等..

谢谢你。

一个 n 括号序列由 n 个“(”s 和 n 个“)”s 组成。

一个有效的括号序列定义如下：

您可以找到一种方法来重复擦除相邻的一对括号“（）”，直到它变空。

例如，"(())" 是一个有效的括号，你可以删除第 2 和第 3 个位置的对，它变成 "()"，然后你可以把它留空。")()(" 不是一个有效的括号，在你擦除第 2 和第 3 位置的对后，它变成了 ")(" 并且你不能再擦除了。

现在，我们有了所有有效的 n 个括号序列。按字典顺序查找第 k 个最小的序列。

例如，以下是按字典顺序排列的所有有效的 3 个括号序列：

来源：https ://code.google.com/codejam/contest/4214486/dashboard#s=p3

注意：比赛现已结束，解决方案可供下载。

我已经通过使用 C++ STL 中可用的 next_permutation()解决了小输入（ k < 10 ^{6 ）的问题。}我无法为此制定一个子问题。我试图通过使用加泰罗尼亚语的号码来解决这个问题，但似乎没有取得任何成功。我不想看到解决方案，因为它对学习没有帮助。请帮助我确定一个子问题。

以下函数生成加泰罗尼亚数字中的第 n 个数字。该函数的确切时间复杂度函数是多少，或者我自己如何找到它？

注意：我知道这是计算加泰罗尼亚数字的最糟糕的方法。

给定以下数据类型定义：

我想编写一个函数，它生成一个无限列表，其中包含按长度排序的所有可能的树，例如节点的数量。

下面的代码几乎可以满足我的需要，但它只会通过每次插入额外的节点来下降右侧的树，但我需要它在两侧交替。

执行

给出：

但它应该是这样的：

处理平衡和不平衡的二叉树。

我正在研究加泰罗尼亚函数，但它并没有给我带来任何好处，主要是因为我认为它可能会计算小于高度 h 的树木。例如，如果高度为 2，我相信它也会计算高度 1（也许高度为 0）。

让我先说一下，我完全是 python 新手，并且为此编程，我需要创建一个程序来打印所有加泰罗尼亚数字，最多可达一万亿。我已经写出了程序的基础知识，但我似乎无法理解为什么我没有得到正确的数字。当我试图绘制趋势图时，我也遇到了一些程序。在此先感谢，这是我的代码：

我正在尝试编写一个迭代的加泰罗尼亚数字生成器，而不是一个递归的。它有效，但直到数字“10”，然后它开始打印出没有意义的数字。这是我到目前为止所拥有的。

}

我一直在使用它作为主要测试它：

哪个返回

哪些是 2 到 10 之间的偶数对应的加泰罗尼亚数字，但在那之后这些值没有多大意义，我不知道为什么。任何帮助解决这个问题将不胜感激。

我是 Python 新手。这是一个家庭作业问题，但它很难，因为我只有一点 Java 经验。该代码应该使用其递归定义打印第一个加泰罗尼亚数字：

编辑：

我当前的代码看起来像这样，唯一剩下的问题是使用 savetxt() 方法将我通过此代码获得的所有 C(n) 数字放入 txt 中。

解决最后一个问题后，我将尝试答案中建议的其他版本（例如先填充零数组）。

这是Cracking the Coding Interview（第5^版）中的问题9.6

实现一个算法来打印 n 对括号的所有有效组合
示例
输入：3
输出："((()))、(()())、(())()、()(())、( )()()"

这是我实现的算法（在 Java 中）

这会产生正确的输出。我知道面试官（至少在亚马逊）喜欢问你解决方案的时间和空间复杂性。对于时间复杂度，我能够证明该算法在O(n)中运行，具有递归关系。我在分析空间复杂度时遇到了麻烦。我这是一个递归解决方案，所以它至少应该是O(n)但是在每次递归调用时，我也会生成一个以 n 为界的集合。由于 n 次递归调用，总空间是O(n)还是因为每个递归调用 n 的边界 n 的设置大小而为O(n ² ) ？