পাইথন প্রোগ্রাম - n নোড দিয়ে BST-এর সংখ্যা বের করুন

মনে করুন n ভিন্ন নোড আছে। সব আলাদা। আমাদের কত প্রকারে সেগুলো বাইনারি সার্চ ট্রি গঠন করা যায় তা বের করতে হবে। বাইনারি সার্চ ট্রিতে বাম সাবট্রি সবসময় ছোট মান এবং ডান সাবট্রি বড় মান ধারণ করে।

এটি ক্যাটালান সংখ্যা বের করে সমাধান করা হয়। ক্যাটালান সংখ্যা C(n) n ভিন্ন কী সহ বাইনারি সার্চ ট্রি প্রতিনিধিত্ব করে। সূত্র:

$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$

ইনপুট n = 3 হলে আউটপুট হবে ৫।

সমাধানের ধাপসমূহ:

ncr() ফাংশন ডিফাইন করুন যা n, r নেয়
res := 1
যদি r > n - r: r := n - r
i = 0 থেকে r-1 পর্যন্ত:
- res := res * (n - i)
- res := floor(res / (i + 1))
res ফেরত দিন
মূল পদ্ধতিতে: c := ncr(2*n, n), floor(c / (n + 1)) ফেরত দিন

উদাহরণ

বাস্তবায়ন:

from math import factorial

def ncr(n, r):
    res = 1
    if r > n - r:
        r = n - r
    for i in range(r):
        res *= (n - i)
        res //= (i + 1)
    return res

def solve(n):
    c = ncr(2 * n, n)
    return c // (n + 1)

n = 3
print(solve(n))