问题标签 [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.
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 的加泰罗尼亚附录。)
algorithm - 使用单个堆栈生成排列
任何人都可以解释算法以在仅使用单个堆栈时生成可能的排列,并且推送和弹出是唯一允许的操作。搜索了很多,但没有明确的答案。这种排列的总数也由加泰罗尼亚数字给出。但我没有得到证明。如果可能的话,请解释一下。
谢谢!!
algorithm - 资质谜题
考虑笛卡尔坐标系中的一个点 P(n,n)。机器人必须从原点开始并到达这一点。机器人可以采取的唯一步骤是:
- 1个单位权利
- 1个单位。
机器人到 P 点可以走多少条不同的路径?
是否有到达 P 点的最优路径?(向上和向右的步骤都会产生相同的成本)。
binary-tree - 计算具有 i 个节点的二叉树的数量
让是具有节点bi
的二叉树的数量。i
计算b10
。
这是我遇到的一个问题。
到目前为止,我已经能够提出这些:
随着我变大,它很快变得有点太多了。
谁能想到比仅仅画出树并计算它们更好的方法来计算 Bi?
algorithm - 下一个语法的复杂度是多少
我正在开发一个通用解析算法,我正在使用下一条规则对其进行测试
好吧,该算法向我展示了为由n a
's 组成的字符串生成的所有树。
例如,下表显示了算法使用的时间,因为a
's的数量
我不知道O
我的算法是什么(大 O 表示法)。我如何测量它,因为时间当然取决于三件事:
- 要解析的字符串的长度
- 语法复杂度
- 算法的性能
recursion - 用动态规划编写递归算法
我想使用动态编程技术编写一个算法,该算法执行以下操作:查找沿具有 n × n 方形单元格的网格边缘的单调路径数,这些单元格不超过对角线。单调路径是从左下角开始,在右上角结束,并且完全由指向右侧或向上的边组成的路径。
我有一些想法,但无法弄清楚如何正确地做到这一点。
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 ?
谢谢
java - 如何找到可能的二叉树拓扑排列的数量?
给定二叉树节点数 (X) 写入方法,该方法返回具有 X 节点的二叉树的随机排列数。
例子:
X=1:1
X=2:2
X=3:5
我最终得到:
我很感激在这里分享更好的解决方案。
algorithm - 给定一个已排序的整数数组,如何从它形成二叉搜索树?
考虑我有一个数组[3,18,15,25,26]
,可以从中形成多少个可能的二叉搜索树?
c++ - 找到第 n 个加泰罗尼亚数 mod m 的最快(已知)算法是什么?
问题是要找到第n 个加泰罗尼亚数 mod m
,其中m
不是素数,m = (10^14 + 7)
。以下是我尝试过的方法列表:(max N = 10,000
)
- 查表的动态编程,太慢了
- 使用加泰罗尼亚公式
ncr(2*n, n)/(n + 1)
,由于函数的原因,它又不够快,不能使用指数平方ncr
加速,因为它不是素数。m
- 对预先生成的表进行硬编码
Catalans
,但由于文件大小限制而失败。 - 递归关系
C(i,k) = C(i-1,k-1) + C(i-1,k)
,这太慢了
所以我想知道有没有其他更快的算法来找到我不知道的第 n 个加泰罗尼亚数字?
使用动态规划
使用原始公式
使用递归关系