Programme C pour le nième numéro catalan

Étant donné un n entier; la tâche est de trouver le numéro catalan sur cette nième position. Donc, avant de faire le programme, nous devons savoir ce qu'est un nombre catalan ?

Les nombres catalans sont la séquence de nombres naturels, qui se présente sous la forme de divers problèmes de comptage de nombres.

Les nombres catalans C0, C1, C2,… Cn sont piloté par la formule −

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

Le quelques nombres catalans pour chaque n = 0, 1, 2, 3, … sont 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Donc si nous entrons n =3 nous devrions obtenir 5 comme résultat du programme

Certaines des rares applications des nombres catalans −

• Compter le nombre d'arbres de recherche binaires possibles avec n clés.
• Trouver le nombre d'expressions contenant n paire de parenthèses qui correspondent correctement. Comme pour n = 3, l'expression entre parenthèses possible serait ((())), ()(()), ()()(), (())(), (()()).
• Trouver le numéro de façons de connecter des points sur des accords disjoints de cercle, et bien d'autres encore.
输入n。

检查如果n < ; = 1.结果。

算法

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

Exemple的中文翻译为：

示例

Start
   Step 1 -> In function 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
   Step 2 -> int main()
   Declare an input n = 6
   Print "catalan is : then call function catalan(n)
Stop

• 输出

#include <stdio.h>
// using recursive approach to find the catalan number
unsigned long int catalan(unsigned int n) {
   // Base case
   if (n <= 1) return 1;
   // catalan(n) is sum of catalan(i)*catalan(n-i-1)
   unsigned long int res = 0;
   for (int i=0; i<n; i++)
      res += catalan(i)*catalan(n-i-1);
   return res;
}
//Main function
int main() {
   int n = 6;
   printf("catalan is :%ld</p><p>", catalan(n));
   return 0;
}

• Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!