第n个加泰罗尼亚语编号C程序

Data l'intero n; il compito è trovare il numero catalano alla posizione n. Quindi, prima di eseguire il programma, dobbiamo sapere cosa sono i numeri catalani?

I numeri catalani sono una sequenza di numeri naturali che si presentano in vari problemi di conteggio.

I numeri catalani C0, C1, C2, ... Cn sono determinati dalla formula-

$$c_{n} = \frac {1} {n + 1} \binom {2n} {n} = \frac {2n!} {(n + 1)!n!} $$

I numeri catalani per n = 0, 1, 2, 3, ... sono1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862...

Dunque, se inseriamo n = 3, dovremmo ottenere come output 5 dal programma

Alcune applicazioni dei numeri catalani-

• Calcolare il numero di alberi di ricerca binari possibili con n chiavi.

• Calcolare il numero di espressioni che contengono n paia di parentesi correttamente abbinati. Come per n = 3, gli espressioni di parentesi possibili sono ((())), ()(()), ()()(), (()()), ()().

• Metodo per trovare i punti di connessione sulle corde non intersecanti di un cerchio, ecc.

示例

Input: n = 6
Output: 132
Input: n = 8
Output: 1430

我们将用来解决给定问题的方法-

• 取并输入n。

• 检查n <= 1，然后返回1

• 从i = 0循环到i <n和i ++

• 对于每个i 设置结果=结果+（catalan(i) * catalan(n-i-1)）

• 返回并打印结果。

算法

Start
　　　步骤1 -> 在函数unsigned long int catalan(unsigned int n)
　　　　　　If n <= 1 then,
　　　　　　　　　Return 1
　　　　　　End if
　　　　　　Declare an unsigned long variable res = 0
　　　　　　Loop For i=0 and i<n and i++
　　　　　　　　　Set res = res + (catalan(i) * catalan(n - i - 1))
　　　　　　End Loop
　　　　　　Return res
　　　步骤2 -> int main() Declare an input n = 6
　　　打印"Catalano è: 然后调用函数catalan(n)
Stop

示例

#include <stdio.h>
//使用递归方法找到加泰罗尼亚数字
unsigned long int catalan(unsigned int n) {
　　　//基本情况
　　　if (n <= 1) return 1;
　　　//加泰罗尼亚语(n)是加泰罗尼亚语(i)*加泰罗尼亚语(n-i-1)的总和
　　　unsigned long int res = 0;
　　　for (int i = 0; i < n; i++)
　　　　　　res += catalan(i) * catalan(n - i - 1);
　　　return res;
}
//主要功能
int main() {
　　　int n = 6;
　　　printf("Catalano è: %ld\n", catalan(n));
　　　return 0;
}

输出结果

Catalano è: 132