标签: catalan

对于二叉树:没有必要考虑树节点值,我只对具有'N'节点的不同树拓扑感兴趣.

对于二进制搜索树:我们必须考虑树节点值.

这是在与朋友交谈时提出的,我想我会问这里,因为这是一个有趣的问题,并希望看到其他人的解决方案.

任务是编写一个函数Brackets(int n),它打印1 ... n 中格式正确的括号的所有组合.对于Brackets(3),输出将是

()
(())  ()()   
((()))  (()())  (())()  ()(())  ()()()

问题是要找到第n个加泰罗尼亚数模m,其中m是不是素数,m = (10^14 + 7).以下是我尝试过的方法列表:(最大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个加泰罗尼亚数字吗？

使用动态编程

void generate_catalan_numbers() {
    catalan[1] = 1;
    for (int i = 2; i <= MAX_NUMBERS; i++) {
        for (int j = 1; j <= i - 1; j++) {
            catalan[i] = (catalan[i] + ((catalan[j]) * …

我有用二项式系数法计算加泰罗尼亚数的代码.

def BinominalCoefficient(n,k):
    res = 1;
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res /= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(510))

当我尝试计算n大于510的加泰罗尼亚数字时,我有一个"纳"结果.为什么会发生这种情况？我该如何解决？

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

我们有n个人坐在圆桌旁.任何人都可以与任何其他人握手.这些人可以通过多少方式进行握手,这样就不会有两次握手相互交叉.

我在技术访谈论坛中发现了这个难题,但没有答案.我能想到的一种方法是找到握手的所有排列,然后检查每个排列是否满足.

任何人都可以请求任何其他更有效的解决方案.

@edit:评论澄清:N会是均匀的.

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

(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))

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

2n个元素的任何有效的括号表达式也会一定ñ (和n )与,从左至右,有至少许多人总是财产(作为).

我知道对于n个数字,方式的数量是第(n-1)个加泰罗尼亚数字.但是,如何准确地生成所有结果分组？

谢谢

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

假设我们将考虑具有长度2n且n可能是大约的二进制数1000.我们正在寻找具有以下特性的kth数字(k受限制10^9):

• 金额1's等于0's可以描述如下的金额:#(1) = #(0)
• 这个数字的每个前缀都有到ATLEAST包含尽可能多0's的1's.在否定句子后可能更容易理解它,即:没有包含1's多于的前缀0's.

基本上就是这样.所以为了说清楚,让我们做一些例子: n=2,k=2 我们必须采用二进制数量的长度2n:

0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...

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

那么我到目前为止所做的算法呢？

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

另外我意识到没有必要检查所有小于0011for n=2,000111for n=3等的数字......坦率地说,那些最重要位的一半仍保持"未被触及",因为这些数字不可能满足#(1) = #(0) …

我试图做经典问题来实现一种算法来打印 n 对括号的所有有效组合。

我找到了这个程序（完美运行）：

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, …

我试图做经典问题来实现一个算法来打印n对括号的所有有效组合.我发现这个程序(完美地运行):

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1); …