问题标签 [catalan]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
9 回答
9185 浏览

algorithm - 如何打印表达式的所有可能的平衡括号?

例如,对于 elements a,b,c,d,有 5 种可能的方式来获取相邻元素并将它们缩减为单个元素,其中必须一次组合两个元素(以下用括号表示):

第一个示例相乘a*b,然后将该乘积乘以 ,然后将该乘积c乘以d。第二个示例首先乘以b*c,然后乘以乘积a,然后乘以乘积d

任何 2n 个元素的有效括号表达式都必须具有 n(和 n)的属性,从左到右阅读,总是至少().

我知道对于 n 个数字,方式的数量是 (n-1)th Catalan number。但是如何准确地生成所有结果分组?

谢谢

(顺便说一句:这个问题有超过 160 种等效公式,所有公式都基于加泰罗尼亚数字枚举的不同组合对象。有关这些的最新列表,请参阅Richard Stanley 的加泰罗尼亚附录。)

0 投票
3 回答
10354 浏览

algorithm - 使用单个堆栈生成排列

任何人都可以解释算法以在仅使用单个堆栈时生成可能的排列,并且推送和弹出是唯一允许的操作。搜索了很多,但没有明确的答案。这种排列的总数也由加泰罗尼亚数字给出。但我没有得到证明。如果可能的话,请解释一下。

谢谢!!

0 投票
3 回答
1111 浏览

algorithm - 资质谜题

考虑笛卡尔坐标系中的一个点 P(n,n)。机器人必须从原点开始并到达这一点。机器人可以采取的唯一步骤是:

  • 1个单位权利
  • 1个单位。

机器人到 P 点可以走多少条不同的路径?

是否有到达 P 点的最优路径?(向上和向右的步骤都会产生相同的成本)。

0 投票
1 回答
217 浏览

binary-tree - 计算具有 i 个节点的二叉树的数量

让是具有节点bi的二叉树的数量。i计算b10

这是我遇到的一个问题。

到目前为止,我已经能够提出这些:

随着我变大,它很快变得有点太多了。

谁能想到比仅仅画出树并计算它们更好的方法来计算 Bi?

0 投票
3 回答
88 浏览

algorithm - 下一个语法的复杂度是多少

我正在开发一个通用解析算法,我正在使用下一条规则对其进行测试

好吧,该算法向我展示了为由n a's 组成的字符串生成的所有树。

例如,下表显示了算法使用的时间,因为a's的数量

我不知道O我的算法是什么(大 O 表示法)。我如何测量它,因为时间当然取决于三件事:

  1. 要解析的字符串的长度
  2. 语法复杂度
  3. 算法的性能
0 投票
3 回答
918 浏览

recursion - 用动态规划编写递归算法

我想使用动态编程技术编写一个算法,该算法执行以下操作:查找沿具有 n × n 方形单元格的网格边缘的单调路径数,这些单元格不超过对角线。单调路径是从左下角开始,在右上角结束,并且完全由指向右侧或向上的边组成的路径。

我有一些想法,但无法弄清楚如何正确地做到这一点。

0 投票
1 回答
356 浏览

excel - 如何在Excel中使用递归来做加泰罗尼亚数?

我尝试在 Excel 中使用 N 值进行以下操作:

http://upload.wikimedia.org/math/b/a/d/bad5db400fcfd7092e2008e376993a27.png

我可以使用 =COMBIN(2*N;N)/(N+1) 制作 Ci,但是考虑到我的 n >= 0,如何制作 ni-1 ?

谢谢

0 投票
3 回答
2165 浏览

java - 如何找到可能的二叉树拓扑排列的数量?

给定二叉树节点数 (X) 写入方法,该方法返回具有 X 节点的二叉树的随机排列数。

例子:

X=1:1

X=2:2

X=3:5

我最终得到:

我很感激在这里分享更好的解决方案。

0 投票
3 回答
6098 浏览

algorithm - 给定一个已排序的整数数组,如何从它形成二叉搜索树?

考虑我有一个数组[3,18,15,25,26],可以从中形成多少个可能的二叉搜索树?

0 投票
2 回答
5598 浏览

c++ - 找到第 n 个加泰罗尼亚数 mod m 的最快(已知)算法是什么?

问题是要找到第n 个加泰罗尼亚数 mod m,其中m不是素数m = (10^14 + 7)。以下是我尝试过的方法列表:(max N = 10,000

  1. 查表的动态编程,太慢了
  2. 使用加泰罗尼亚公式ncr(2*n, n)/(n + 1),由于函数的原因,它又不够快,不能使用指数平方ncr加速,因为它不是素数。m
  3. 对预先生成的表进行硬编码Catalans,但由于文件大小限制而失败。
  4. 递归关系C(i,k) = C(i-1,k-1) + C(i-1,k),这太慢了

所以我想知道有没有其他更快的算法来找到我不知道的第 n 个加泰罗尼亚数字?

使用动态规划

使用原始公式

使用递归关系