1

我创建了一个 C 程序，它给出了第 n 个加泰罗尼亚语数字。到目前为止一切正常。这里是：

#include <stdio.h>

int catalan(int);

main()
{
    int number, catalannumber;

    printf("This is a program to find a given catalan number.\nIntroduce your desired number: ");
    scanf("%d", &number);

    while (number < 1)
    {
        printf("Number must be greater or equal to 1. Reintroduce: ");
        scanf("%d", &number);
    }

    catalannumber = catalan (number);

    printf("The %dth number corresponds to %d.\n", number, catalannumber);
}

int catalan(int n) {
  if (n == 1)
    return 1; 
  else
    return 2 * (2*n - 1) * catalan(n-1) / (n+1);
}

然后我发现了这个“经典”山脉问题，图中所有可能的山脉：http: //www.maths.usyd.edu.au/u/kooc/catalan/cat3moun.pdf

这是源值较小的“山脉”的样子n 在此处输入图像描述

我的目标是能够创建一个程序：

  1. 一旦你给他们这个数字，你就可以选择“山顶”的数量（<= number）

  2. 该程序将计算（给定数量的）有多少不同的山脉具有该数量的山顶。

通过pdf文件，我知道：

  1. number n = 3 & “mountain tops” = 2 -> 有 3 个（总共 5 个）山脉，有 2 个山顶（都是不同的山“类型”）。

  2. 数字 n = 4 & “山顶” = 3 -> 6 个不同的山脉。

我的问题是，做这项工作的最佳方法是什么？有什么公式吗？我想过帕斯卡三角形和斐波那契数列，但我没有发现它们之间有任何关系。我想知道什么是可能的解决方案。任何帮助都将得到真正的赞赏。谢谢。

4

1 回答 1

3

让我们先看看蛮力方法。

加泰罗尼亚数c n是在不低于地平线的情况下，可以组合n次上行 (╱) 和n次下行 (╲) 的方式数。根据定义， cn = ( n + 2)/2 · (n + 3)/3 · ... (n + n)/n。

我们可以使用无符号的 2 n位整数来描述每个组合。（但是，并非所有 2 n位无符号整数值都描述了有效的组合。）如果我们将非零或设置位视为上行，而将零位视为下行，则每当下行跟随上行时就会出现峰值。（当向下冲程之后是向上冲程时，您有一个山谷。）

（请注意，并非所有无符号的 2 n位整数值都描述了有效的组合。要有效，第一位必须是上行，并且必须正好有n 个上行。）

因此，首先编写一个函数，计算由无符号整数描述的一个组合中的峰值数量。（注意，因为描述组合的每个无符号整数都设置了n位，所以我们不需要显式传递n，只需要描述组合的无符号整数。）例如，

unsigned int  peaks(unsigned int  description)
{
    unsigned int  count = 0;

    while (description) {
        count += ((description & 3) == 1);
        description >>= 1;
    }

    return count;
}

上面，从最低有效位开始读取组合。（并且因为必须将山脉设置为可能高于地平线，所以没有偶数值描述组合。）该表达式(description & 3)隔离了最后两个有效位。四种可能的情况分别对应于双下坡、峰、谷和双上坡，按数值递增的顺序。峰值情况对应于值 1（二进制中的 01 b：上冲后跟下冲，按照重要性递增的顺序读取数字，从右到左）。在 C 语言中，逻辑False的值为 0，逻辑True的值为 1，因此在上面的循环中，我们得到了设置位之后（在更重要的位置）被清除位的情况的数量。

Value  Mountains       n   Peaks
    1   ╱╲             1     1
    3   ╱╱╲╲           2     1
    5   ╱╲╱╲           2     2
    7   ╱╱╱╲╲╲         3     1
    9   ╱╲╲╱         Not a valid combination
   11   ╱╱╲╱╲╲         3     2
   13   ╱╲╱╱╲╲         3     2
   15   ╱╱╱╱╲╲╲╲       4     1
   17   ╱╲╲╲╱        Not a valid combination
   19   ╱╱╲╲╱╲         3     2
   21   ╱╲╱╲╱╲         3     3
   23   ╱╱╱╲╱╲╲╲       4     2
   25   ╱╲╲╱╱╲       Not a valid combination
   27   ╱╱╲╱╱╲╲╲       4     2
   29   ╱╲╱╱╱╲╲╲       4     2
   31   ╱╱╱╱╱╲╲╲╲╲     5     1
   33   ╱╲╲╲╲╱       Not a valid combination
   35   ╱╱╲╲╲╱       Not a valid combination
   37   ╱╲╱╲╲╱       Not a valid combination
   39   ╱╱╱╲╲╱╲╲       4     2

接下来，创建一个函数，该函数生成所有描述特定n的有效组合的无符号整数值，并计算与特定峰数相对应的那些值。

一种蛮力方法是编写峰值计数函数，使其对所有无效组合返回 0。例如：

static unsigned int  peaks(unsigned int  description)
{
    unsigned int  count = 0;
    int           height = 0;

    /* Description must start with an upstroke. */
    if (!(description & 1))
        return 0;

    while (description) {
        switch (description & 3) {
        case 0: /* Downslope; next is downslope. */
            if (--height < 0)
                return 0;
            break;

        case 1: /* Upslope; next is downslope. */
            count++;
            height++;
            break;

        case 2: /* Downslope; next is upslope. */
            if (--height < 0)
                return 0;
            break;

        default: /* 3: Upslope; next is upslope. */
            height++;

        }

        description >>= 1;
    }

    return count;
}

描述对应的npeak(description) > 0 (if ) 是描述中设置的位数。计算的一个绝妙技巧是

unsigned int  popcount(unsigned int  value)
{
    unsigned int  count = 0;
    while (value) {
        value &= value - 1;
        count++;
    }
    return count;
}

使用这两个函数，您可以通过探索所有 2个 n位无符号整数（从到，包括）来解决小n的所述问题。0(1 << (2*n)) - 1

为了更好的方法，让我们检查每个n的峰值数量：

n Combs   Occurrences*Peaks
0    1     1*0
1    1     1*1
2    2     1*1,  1*2
3    5     1*1,  3*2,  1*3
4   14     1*1,  6*2,  6*3,  1*4
5   42     1*1, 10*2, 20*3, 10*4,  1*5
6  132     1*1, 15*2, 50*3, 50*4, 15*5, 1*6

换句话说，n = 6 有 132 个有效组合。其中，1个峰1个，2个峰15个，3个峰50个，4个峰50个，6个峰1个。

如果我们只是形成峰值计数的整数序列，我们可以将上述表示为

1,
1, 1,
1, 3, 1
1, 6, 6, 1,
1, 10, 20, 10, 1,
1, 15, 50, 50, 15, 1,

以此类推，对于 n = 7 继续使用 1、21、105、175、105、21、1，对于n = 8，继续使用 1、28、196、490、490、196、28、1，依此类推。

如果我们对该序列进行 OEIS 搜索，我们会发现这些实际上称为 Narayana 数T ( n , k )，整个整数序列是OEIS A001263。

（注意：我不知道是这样的！我只知道我可以使用 OEIS 来确定序列是否已知，而且它们通常是已知的。换句话说，我不只是向您展示这个特定问题的答案在这里，但是我如何找到——非常有效，如果我自己可以这么说的话——这类问题的解决方案，从蛮力数值方法开始。）

因此，数学上的答案是，纳拉亚纳数 T ( n , k ) 告诉您与加泰罗尼亚数c n对应的不同山脉的数量，其中恰好有k个峰。

如果您将二项式系数实现为函数binomial(n, k)，那么答案是T(n, k) = binomial(n, k) * binomial(n, k - 1) / n。

但是请注意，您可以更有效地实现术语乘积之间的除法（即，使用两个术语数组，并使用最大公约数T(n, k)辅助函数消除常用术语和术语乘积，而不会因术语取消而导致精度问题.)

于 2018-09-28T01:01:23.317 回答