सी/सी++ एनएच कैटलन नंबर के लिए प्रोग्राम?

कैटलन संख्याएं संख्याओं का एक क्रम है। कैटलन संख्याएं प्राकृतिक संख्याओं का एक क्रम बनाती हैं जो गिनती की विभिन्न समस्याओं में होती हैं, जिनमें अक्सर पुनरावर्ती-परिभाषित वस्तुएं शामिल होती हैं।

• सी<उप>एन लंबाई 2n के डाइक शब्दों की संख्या है। एक डाइक शब्द एक स्ट्रिंग है जिसमें एन एक्स और एन वाई शामिल हैं जैसे कि स्ट्रिंग के किसी भी प्रारंभिक खंड में एक्स से अधिक वाई नहीं है। उदाहरण के लिए, लंबाई 6 के डाइक शब्द निम्नलिखित हैं

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.

• प्रतीक X को एक खुले कोष्ठक के रूप में और Y को एक करीबी कोष्ठक के रूप में फिर से व्याख्या करना, C_n कोष्ठक के n जोड़े वाले भावों की संख्या की गणना करता है जो सही ढंग से मेल खाते हैं

((())) ()(()) ()()() (())() (()())

• सी<उप>एन विभिन्न तरीकों की संख्या है n + 1 कारकों को पूरी तरह से संश्लेषित किया जा सकता है (या बाइनरी ऑपरेटर के n अनुप्रयोगों को जोड़ने के तरीकों की संख्या)। n =3 के लिए, उदाहरण के लिए, हमारे पास चार कारकों के निम्नलिखित पांच अलग-अलग कोष्ठक हैं:

((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))

• बाइनरी ऑपरेटर के क्रमिक अनुप्रयोगों को पूर्ण बाइनरी ट्री के रूप में दर्शाया जा सकता है। (एक रूटेड बाइनरी ट्री भरा होता है यदि प्रत्येक शीर्ष पर या तो दो बच्चे हों या कोई बच्चा न हो।) यह इस प्रकार है कि C_n n + 1 पत्तियों वाले पूर्ण बाइनरी ट्री की संख्या है:

नमूना

इनपुट - 6
आउटपुट - 1 1 2 5 14 42

स्पष्टीकरण

एन =0, 1, 2, 3,4,5,6,7,8,9,10, ... के लिए पहली कैटलन संख्याएं हैं
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,

उदाहरण

#include<iostream>
using namespace std;
long int catalan( int n) {
   if (n <= 1){
      return 1;
   }
   long int result = 0;
   for (int i=0; i<n; i++){
      result += catalan(i)*catalan(n-i-1);
   }
   return result;
}
int main(){
   for (int i=0; i<6; i++)
   cout << catalan(i) << " ";
   return 0;
}

आउटपुट

1 1 2 5 14 42