اعداد کاتالان در سی شارپ (Catalan Number)

در این قسمت تیم کدگیت را با آموزش اعداد کاتالان در سی شارپ همراهی کنید. ابتدای این آموزش دنباله اعداد کاتالان و فرمول آن را بیان می‌کنیم سپس به پیاده سازی آن در زبان سی شارپ می‌پردازیم. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را بخوانید:

1. متد در سی شارپ
2. حلقه For در سی شارپ
3. If در سی شارپ

اعداد کاتالان

دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت Cn نمایش داده می‌شود. این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:

1. تعداد درخت‌های دودویی با n رأس داخلی برابر با Cn است.
2. تعداد پرانتزبندی‌های صحیح با استفاده از n جفت پرانتز باز و بسته برابر Cn است.
3. 3.      …….

برای محاسبه اعداد کاتالان از فرمول زیر استفاده می‌شود.

طبق فرمول بالا، محاسبه اعداد کاتالان به صورت زیر است:

C1 = C0 * C0 = 1 * 1 = 1

C2 = C0*C1 + C1 * C0 = 1 * 1 + 1 * 1 = 2

C3 = C0 * C2 + C1 * C1 + C2 * C0 = 1 * 2 + 1 * 1 + 2 * 1 = 5

اعداد کاتالان در سی شارپ

برای پیاده سازی اعداد کاتالان از یک حلقه For استفاده کرده‌ایم. یک متد به نام catalan نوشته ایم که در ورودی عدد کاتالان درخواستی را دریافت می‌کند. سپس به صورت بازگشتی عدد کاتالان را محاسبه می‌کنیم. کد این مثال به صورت زیر است:

 static int catalan(int n) { 
            int res = 0; 

            // Base case 
            if (n <= 1) { 
                return 1; 
            } 
            for (int i = 0; i < n; i++)  
            { 
                res += catalan(i) 
                    * catalan(n - i - 1); 
            } 
            return res; 
        } 
        public static void Main (string[] args)
        {
            for (int i = 0; i < 10; i++)  
                Console.Write(catalan(i) 
                    + " "); 
            Console.ReadKey ();
        } 

خروجی کد بالا اعداد اول تا دهم کاتالان می‌باشد(بین اعداد به اندازه یک Space فاصله است):

1 1 2 5 14 42 132 429 1430 4862