问题标签 [catalan]

这是作业，我想起来有困难。请给我一些关于递归和DP解决方案的想法。非常感谢

生成并打印所有结构上不同的完整二叉树，其中 n 个叶子以点括号的形式出现，“完整”表示所有内部（非叶子）节点正好有两个子节点。

例如，有 5 棵不同的满二叉树，每棵树有 4 个叶子。

在 Prolog 中生成所有具有 n 个叶子的结构不同的完整二叉树。问题是给定叶子的数量，输出所有不同的完整二叉树。这里的“完整”意味着任何内部节点都必须有两个孩子，左和右。

让我们通过列表来表示树。

如果叶子的数量是两个，A 和 B。那么只有一棵树 (AB)。

如果叶子的数量是三，A，B和C。那么有两棵树（（AB）C）和（A（BC））。

那么如果有 N 片叶子，那么有多少棵树呢？

一个完全没用的问题：我买了一个数字游戏，它是由两个黑色骰子加上 5 个彩色骰子组成的。两个黑色的组成一个 2 位数字，范围从 11 到 66，另外 5 个是您可以使用的数字，将它们以所有可能的数字表达式与任务结合以获得目标数字。

比如黑40+2：目标42

彩色 5 3 6 2 4，可以通过 5 3 + 6 * 4 2 + - 获得目标（使用 RPN，因为它避免了括号）。

现在我想用我的袖珍电脑在我们玩游戏的时候找到最佳答案。

我必须说我还没有真正考虑过解决方案，我只是寻找关于寻找参数排列的部分，但是如何从中生成可能的表达式？我会使用 RPN 并枚举所有可能的表达式“形状”，然后用 +-*/ 填充空格。

我不认识枚举表达式形状的问题。

输出将是这样的： .....xxxx ....x.xxx ...x..xxx ..x...xxx ....xx.xx ...xxxx ..x..x .xx ...xx..xx ..xx.xx ....xxx.x ...x.xx.x ..x..xx.x ...xx.xx ..xxxx

像： ..xx...xx ...xxx..x ..x.xx..x ..x.xx..x 是无效的，因为第二个或第三个运算符会找到一个操作数。

我可以使用硬编码列表，但它看起来真的很难看！

我正在寻找一种实用的算法来枚举所有完整标记的二叉树。

完全二叉树是一棵树，其中所有内部节点的度数为 3，叶子的度数为 1，根的度数为 2。

带标签的树是所有叶子都有唯一标签的树。

例子：

我有一个有趣的组合问题，我有点卡住了

让我们定义一个函数 p(xn)，它返回方程 x 的 '()' 的数量 现在 x 只能是 x1 + x2 + x3 ... xn 这个函数定义为 n >=2

例子：

P(x2) = (x1 + x2) = 1

p(x3) = ((x1 + x2) + x3) 和 (x1 + (x2 + x3))

p(x4) =

((x1 + x2) + (x3 + x4))

((((x1 + x2) + x3) + x4)

((x1 + (x2 + x3)) + x4)

(x1 + ((x2 + x3) + x4))

(x1 + (x2 + (x3 + x4)))

等等 注意 (x1 + (x2 + x3) + x4) 不是一个有效的例子，每个 + 必须有一个 ()

现在，我试图想出一个 P 的公式来确定组合的数量我不确定是否有一个固定的公式或依赖于其先前术语的递归定义。各位大佬能帮我看看公式吗？

我正在计算具有 n 个节点的二叉搜索树的数量，我发现它是加泰罗尼亚数。

现在，使用 DP，这是我的尝试。

这是正确的方法吗？

还能更好吗？

是否可以仅通过遍历的结果，前序，中序和后序来确定两个二叉搜索树的结构等价。假设我只有所有遍历的结果数组。我知道单单为了遍历，没办法。但是，我无法想象其他遍历结果。我了解 BFS 有帮助。我想知道前后顺序遍历。如果可能，请在此发布任何链接。

我正在尝试在数组中插入所有加泰罗尼亚语数字，但我的代码不起作用。

• 描述：将加泰罗尼亚语序列中的元素插入仅针对 C[0] 初始化的给定数组中。
• 输入：数组的地址
  • n：下一个要填补的位置；
  • top：要计算的最大条目数。
• 输出：
  • int：数组中的元素个数。
  • 副作用：更新数组的元素。

代码：

我们有 n 个人坐在一张圆桌上。任何人都可以与任何其他人握手。这 n 个人可以用多少种方式进行握手，以使两次握手不会相互交叉。

我在一个技术面试论坛上发现了这个谜题，但没有答案。我能想到的一种方法是找到握手的所有排列，然后检查每个排列是否满足。

任何人都可以建议任何其他更有效的解决方案。

@edit：来自评论的澄清：N 会是偶数。