একটি ইন্টিজার n দেওয়া থাকলে; টাস্ক হলো সেই nth পজিশনের ক্যাটালান নম্বর বের করা। প্রোগ্রাম করার আগে আমাদের জানতে হবে ক্যাটালান নম্বর কী?
ক্যাটালান নম্বর হলো প্রাকৃতিক সংখ্যার একটি সিকোয়েন্স, যা বিভিন্ন কাউন্টিং সমস্যার রূপে আবির্ভূত হয়।
ক্যাটালান নম্বর C₀, C₁, C₂,… Cₙ নিম্নলিখিত সূত্র থেকে প্রাপ্ত হয় −
$$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
- প্রতিটি i-এর জন্য result = result + (catalan(i)*catalan(n-i-1)) সেট করুন।
- রেজাল্ট রিটার্ন ও প্রিন্ট করুন।
অ্যালগরিদম
Start
ধাপ ১ → function unsigned long int catalan(unsigned int n) এ
If n <= 1 then,
Return 1
End if
unsigned long variable res = 0 ডিক্লেয়ার
লুপ: i=0; i
উদাহরণ
#include <stdio.h>
// রিকার্সিভ পদ্ধতিতে ক্যাটালান নম্বর বের করা
unsigned long int catalan(unsigned int n) {
// বেইস কেস
if (n <= 1) return 1;
// catalan(n) হলো catalan(i)*catalan(n-i-1) এর যোগফল
unsigned long int res = 0;
for (int i=0; i
আউটপুট
catalan is :132
