برنامج C للرقم الكاتالوني nth

لدينا عدد صحيح n; المهمة هي العثور على الرقم الكاتالاني في الموضع n. لذلك، قبل تشغيل البرنامج، يجب أن نعرف ما هو الرقم الكاتالاني؟

رقم الكاتالان هو سلسلة من الأرقام الطبيعية، تظهر في شكل أنواع مختلفة من مشاكل العد.

رقم الكاتالان C0، C1، C2، ... Cn مدفوعًا بالمعادلة

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

رقم الكاتالان لكل n = 0، 1، 2، 3، إلخ هو1، 1، 2، 5، 14، 42، 132، 429، 1430، 4862...

لذلك، إذا كنا ندخل n = 3، يجب أن نحصل على 5 كخروج من البرنامج

تطبيقات بعض الأرقام الكاتالانية-

• حساب عدد الأشجار البحثية المحتملة باستخدام n مفتاحًا.

• عدد التعبيرات التي تحتوي على n زوج من الأقواس المترابطة. مثل n = 3، التعبيرات الممكنة للأقواس هي ((()))، ()(())، ()()()، (()())، (()(())).

• طريقة البحث عن نقاط الاتصال على الأ弓 التي لا تلتقي في الدائرة، إلخ.

مثال

الإدخال: n = 6
الإخراج: 132
الإدخال: n = 8
الإخراج: 1430

سنستخدمها لحل المشكلة المقدمة-

• خذ وادخل n.

• تحقق من n <= 1، ثم العودة إلى 1

• الدورة من i = 0 إلى i <n و i ++

• للمسافة i اجعل النتيجة = النتيجة + (catalan(i)* catalan(ni-1))

• العودة وطباعة النتيجة.

الخوارزمية

البداية
　　　الخطوة 1 -> في الوظيفة unsigned long int catalan(unsigned int n)
　　　　　　إذا كان n <= 1 ثم
　　　　　　　　　العودة إلى 1
　　　　　　انتهاء if
　　　　　　اعلان متغير unsigned long res = 0
　　　　　　دورة لـ i=0 و i<n و i++
　　　　　　　　　اجعل res = res + (catalan(i)*catalan(n-i-1))
　　　　　　انتهاء الدورة
　　　　　　العودة إلى res
　　　الخطوة 2 -> int main() Declare an input n = 6
　　　اطبع "catalan is :" ثم اتصال بوظيفة catalan(n)
توقف

مثال

#include <stdio.h>
//استخدام الطريقة التكرارية لمعرفة الرقم الكاتالوني
unsigned long int catalan(unsigned int n) {
　　　//حالة أساسية
　　　if (n <= 1) return 1;
　　　//النص الكاتالوني(n) هو مجموع النص الكاتالوني(i)*النص الكاتالوني(ni-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("catalan is :%ld\n", catalan(n));
　　　return 0;
}

نتيجة الخروج

catalan is :132