C编程数字和山脉

Question

我创建了一个 C 程序，它给出了第 n 个加泰罗尼亚语 number.Everything 目前正在运行。这是：

#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);
}

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

这是 "mountain ranges" 的小值 n 的样子 source

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

一旦你给了他们号码，你就可以选择 "mountain tops" ( <= number )
该程序会计算（给定数量的）有多少不同的山脉具有该数量的山顶。

通过pdf文件，我知道：

number n = 3 & "mountain tops" = 2 -> 有 3 个（总共 5 个）山脉和 2 个山顶（都是不同的山脉 "types"）。
number n = 4 & "mountain tops" = 3 -> 6 个不同的山脉。

我的问题是，完成这项工作的最佳方法是什么？有什么公式吗？我考虑过 Pascal Triangle 和 Fibonacci 系列，但我没有发现它们之间有任何关系。我想知道什么是可能的解决方案。我们将不胜感激任何帮助。谢谢。

Answer 1

让我们先看看蛮力方法。

加泰罗尼亚数字 c_n 是可以组合 n 上击的方式数 ( ╱) 和 n 下击 (╲) 而不会低于 horizon。根据定义，c_n = (n + 2)/2 · (n + 3)/3 · ... (n + n) /n.

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

(请注意，并非所有无符号 2n 位整数值都描述了有效组合。要有效，第一位必须是上划线，并且必须正好 n 笔划。)

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

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

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

    return count;
}

以上，组合是从最低有效位开始读取的。（并且因为必须将山脉设置为可能高于 horizon，所以没有偶数值描述组合。）表达式 (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 的有效组合的无符号整数值，并计算与特定数量的峰值相对应的值。

一种蛮力方法是编写 peak-counting 函数，使其 returns 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;
}

一个描述对应的n（如果peak(description) > 0），就是描述中设置的位数。一个漂亮的计数技巧是

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

使用这两个函数，您可以通过探索所有 2n 位无符号整数（从 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个，二峰15个，三峰50个，四峰50个，六峰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，以及 1、28、196、490、490 , 196, 28, 1 为 n=8，依此类推。

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

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

所以，数学答案是 Narayana number T(n,k)告诉你加泰罗尼亚数c_n对应的不同山脉的数量恰好是k峰值。

如果将 binomial coefficient 实现为函数 binomial(n, k)，则答案为 T(n, k) = binomial(n, k) * binomial(n, k - 1) / n。

但是请注意，您可以将 T(n, k) 更有效地实现为项乘积之间的除法（即，使用两个项数组，并使用 greatest common divisor 辅助函数，没有因取消项而导致的精度问题。）

C编程数字和山脉

C programming numbers and mountains

c

math

catalan