C-Programm für die n-te katalanische Nummer C

Gegeben eine ganze Zahl n; Die Aufgabe ist es, an der n-ten Stelle den Catalan-Code zu finden. Daher müssen wir vor der Ausführung des Programms wissen, was eine katalanische Zahl ist?

Die Catalan-Zahlen sind eine Sequenz natürlicher Zahlen, die in der Form von verschiedenen Zählungsproblemen auftreten.

Die katalanische Zahl C0, C1，C2，... Cn wird durch die Formel bestimmt-

$$c_ {n} = \frac {1} {n + 1} \binom {2n} {n} = \frac {2n！} {（n + 1）！n！} $$

Für n = 0、1、2、3，... Die katalanische Zahl ist1、1、2、5、14、42、132、429、1430、4862 ...

Daher, wenn wir n = eingeben 3， wir sollten aus dem Programm erhalten5Als Ausgabe

Einige Anwendungen der Katalanischen Zahlen-

• Berechne die Anzahl der möglichen Binärbäume mit n Schlüsseln.

• Finden Sie die Anzahl der Ausdrücke, die n Paare von korrekt übereinstimmenden Klammern enthalten. Wie n = 3Gleichzeitig sind mögliche Klammern Ausdrücke ((()))，()(()), ()()()，(()())，(()()).

• Suchen Sie Methoden, um Punkte zu verbinden, die auf不相交的弧上，等等。

Beispiel

Eingabe: n =　6
Ausgabe:　132
Eingabe: n =　8
Ausgabe:　1430

Wir werden die Methode verwenden, um das Problem zu lösen-

• Nimm und gebe n ein.

• Überprüfe n <= 1Dann kehre zurück1

• Schleife von i = 0 bis i < n und i ++

• Für jeden i Setze den Wert = Wert+（catalan(i)* catalan(ni-1)）

• Gib das Ergebnis zurück und drucke es aus.

Algorithmus

Start
　　　Schritt　1　-> In der Funktion unsigned long int catalan(unsigned int n)
　　　　　　Wenn n <=　1　dann,
　　　　　　　　　Rückgabe　1
　　　　　　Ende des Falls
　　　　　　Erkläre eine unsigned long Variable res = 0
　　　　　　Schleife für i = 0 und i < n und i++
　　　　　　　　　Setze res = res　+　(catalan(i)*catalan(n-i-1))
　　　　　　Ende der Schleife
　　　　　　Rückgabe res
　　　Schritt　2　-> int main() Declare an input n =　6
　　　Drucke "catalan ist :" und rufe die Funktion catalan(n) auf
Stop

Beispiel

#include <stdio.h>
//Finden Sie die Katalanischen Zahlen mit rekursiver Methode
unsigned long int catalan(unsigned int n) {
　　　//Grundlagenfall
　　　if (n <=　1) return　1;
　　　//Katalanische Sprache(n) ist Katalanische Sprache(i)*Katalanische Sprache(ni-1) Summe
　　　unsigned long int res = 0;
　　　for (int i = 0; i < n; i++)
　　　　　　res　+= catalan(i)*catalan(n-i-1);
　　　return res;
}
//Hauptfunktion
int main() {
　　　int n =　6;
　　　printf("catalan ist : %ld\n", catalan(n));
　　　return 0;
}

Ausgabeergebnis

catalan ist :132