ধরুন আমাদের একটি স্ট্রিং আছে যার A এর n সংখ্যা এবং B এর 2n সংখ্যা রয়েছে। আমাদের সম্ভাব্য বিন্যাসের সংখ্যা খুঁজে বের করতে হবে যাতে প্রতিটি উপসর্গ এবং প্রতিটি প্রত্যয় এ A এর সংখ্যার চেয়ে বড় বা সমান B এর সংখ্যা থাকে
সুতরাং, যদি ইনপুটটি n =2 এর মত হয়, তাহলে আউটপুট 4 হবে কারণ দুটি A' এবং চারটি B আছে, তাই সম্ভাব্য বিন্যাস হল [BBAABB, BABABB, BBABAB, BABBAB]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি সমাধানের পদ্ধতি নির্ধারণ করুন, এটি n লাগবে
- যদি n 1 এর মত হয়, তাহলে
- প্রত্যাবর্তন 1
- যদি n 2 এর মত হয়, তাহলে
- প্রত্যাবর্তন 4
- যদি n বিজোড় হয়, তাহলে
- রিটার্ন খুঁজুন((n-1)/2)^2
- অন্যথায়,
- রিটার্ন ফাইন্ড(n/2 এর ফ্লোর)^2
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(n): if n==1: return 1 if n==2: return 4 if n%2 != 0: return solve((n-1)//2)**2 else: return solve(n//2)**2 n = 2 print(solve(n))
ইনপুট
2
আউটপুট
4