در این قسمت تیم کدگیت را با آموزش اعداد کاتالان در جاوا همراهی کنید. ابتدای این آموزش دنباله اعداد کاتالان و فرمول آن را بیان خواهیم کرد سپس به پیاده سازی آن در زبان جاوا می‌پردازیم. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را بخوانید:
اعداد کاتالان
دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت Cn نمایش داده می‌شود. این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:
- تعداد درخت‌های دودویی با n رأس داخلی برابر با Cn است.
- تعداد پرانتزبندی‌های صحیح با استفاده از n جفت پرانتز باز و بسته برابر Cn است.
- تعداد روش‌های مثلث‌بندی یک چندضلعی محدب با n + 2 ضلع برابر Cn است.
- تعداد پرانتزبندی‌های صحیح n عبارت ریاضی برابر Cn-1 است.
برای محاسبه اعداد کاتالان از فرمول زیر استفاده می‌شود.
طبق فرمول بالا، محاسبه اعداد کاتالان به صورت زیر است:
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 نوشته ایم که در ورودی عدد کاتالان درخواستی را دریافت می‌کند. سپس به صورت بازگشتی عدد کاتالان را محاسبه می‌کنیم. کد این مثال به صورت زیر است:
int catalan(int n) {
int res = 0;
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) {
CatalnNumber cn = new CatalnNumber();
for (int i = 0; i < 10; i++) {
System.out.print(cn.catalan(i) + " ");
}
}
خروجی کد بالا اعداد اول تا دهم کاتالان می‌باشد(بین اعداد به اندازه یک Space فاصله است):
1 1 2 5 14 42 132 429 1430 4862