我创建了一个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
以下是“山脉”的小值
nsource
我的目标是能够创建一个程序：
一旦你给了他们号码，你就可以选择“山顶”的号码（这个程序会计算出有多少不同的山脉（在给定的数字中）有那么多的山顶。
根据pdf文件，我知道：
数字n=3&“山顶”=2->有3个（共5个）山脉有2个山顶（两个不同的山“类型”）。
数字n=4&“山顶”=3->6个不同的山脉。
我的问题是，做这项工作的最好方法是什么？有什么公式吗？我考虑过帕斯卡三角和斐波那契级数，但没有发现它们之间的任何关系。我想知道什么是可能的解决办法。
任何帮助都将得到真正的补偿。谢谢。
最佳答案
让我们先来看看暴力手段。
加泰罗尼亚数字cn是一个人可以组合n次上击（╱）和n次下击（╲）而不低于地平线的方式。根据定义，cn=（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;
}
上面，从最低有效位开始读取组合。（因为它必须设置为山脉可能在地平线以上，所以没有偶数值描述组合。）表达式
(description & 3)隔离了最后两个有效位。这四种可能的情况分别对应于双下坡、峰、谷和双上坡，以增加数值。峰值情况对应于值1（二进制为01b：上行程后下行程，从右向左按显著性递增顺序读取数字）。在C中，逻辑False的值为零，逻辑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;
}
描述对应的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的峰值数：
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, 1,
1, 3, 1
1, 6, 6, 1,
1, 10, 20, 10, 1,
1, 15, 50, 50, 15, 1,
以此类推，继续1，21，105，175，105，21，1表示n=7，继续1，28，196，490，490，196，28，1表示n=8，依此类推。
如果我们对这个序列进行OEIS搜索，我们会发现它们实际上被称为Narayana数T（n，k），整个整数序列是OEIS A001263。
（注：我不知道是这样！我只知道我可以使用OEIS来确定序列是否已知，而且它们通常是已知的。换言之，我不仅仅是在这里向您展示这个问题的答案，而是如何找到——如果我可以自己这么说的话——这类问题的解决方案，从一种暴力的数值方法开始。）
因此，数学上的答案是，Narayana numberT（n，k）告诉你对应于加泰罗尼亚数cn的不同山脉的数目，正好有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编程数字和山脉，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52545884/