একটি ইন্টিজার N ইনপুট হিসেবে দেওয়া আছে যা একটি সার্কেলে 2*N এন্ডপয়েন্টসহ চর্ডের সংখ্যা নির্দেশ করে। লক্ষ্য হলো সার্কেলকে এসব চর্ড দিয়ে কতভাবে ভাগ করা যায় যাতে কোনো চর্ড অন্য চর্ডের সাথে ইন্টারসেক্ট না করে।
N=3 হলে পয়েন্ট হবে ৬, ৩টি চর্ড পাওয়ার ১ পদ্ধতি: ১-২, ৩-৪, ৫-৬
অন্যান্য পদ্ধতিগুলো:
১-৬, ২-৫, ৩-৪ ১-২, ৩-৬, ৪-৫ ১-৪, ২-৩, ৫-৬ ১-৬, ২-৩, ৪-৫
মোট ৫ পদ্ধতি।
উদাহরণ ১
ইনপুট
N=4
আউটপুট
N নন-ইন্টারসেক্টিং চর্ড দিয়ে সার্কেল ভাগ করার পদ্ধতির সংখ্যা: 14
ব্যাখ্যা
মোট ৮টি পয়েন্ট থাকবে চর্ড আঁকতে। প্রথম চর্ড আঁকে দিলে বাকি পয়েন্টগুলো দুটি সেটে ভাগ হবে। সেট ১ এবং সেট ২-এর পয়েন্টগুলোর মধ্যে চর্ড আঁকলে সেটি প্রথম চর্ডের সাথে ইন্টারসেক্ট করবে।
উদাহরণ ২
ইনপুট
N=6
আউটপুট
N নন-ইন্টারসেক্টিং চর্ড দিয়ে সার্কেল ভাগ করার পদ্ধতির সংখ্যা: 132
ব্যাখ্যা
মোট ১২টি পয়েন্ট থাকবে চর্ড আঁকতে। প্রথম চর্ড আঁকে দিলে বাকি পয়েন্টগুলো দুটি সেটে ভাগ হবে। সেট ১ এবং সেট ২-এর পয়েন্টগুলোর মধ্যে চর্ড আঁকলে সেটি প্রথম চর্ডের সাথে ইন্টারসেক্ট করবে।
প্রয়োগ করা পদ্ধতি
এই পদ্ধতিতে আগের কাউন্ট ব্যবহার করে পদ্ধতি গণনা করা হয়। যদি ২টি পয়েন্টের মধ্যে যেকোনো চর্ড আঁকা হয়, বাকি পয়েন্টগুলো দুটি সেটে set1 এবং set2-এ ভাগ হবে। যদি এই দুটি সেটের পয়েন্টগুলোর মধ্যে চর্ড আঁকা হয় তবে সেগুলো প্রথম চর্ডের সাথে ইন্টারসেক্ট করবে।
ইনপুট হিসেবে ইন্টিজার
Nনিন।divide_circle(int N)ফাংশনটি পদ্ধতির সংখ্যা রিটার্ন করে।মোট পয়েন্ট =
2*Nহিসেবেtotal_points।total_cuts[]অ্যারে নিন পদ্ধতির কাউন্ট সংরক্ষণের জন্য।০ বা ২ পয়েন্টের জন্য মাত্র ১ পদ্ধতি, তাই
total_cuts[0],total_cuts[2]১ দিয়ে আরম্ভ করুন।বাকি পয়েন্টগুলোর জন্য
points=4থেকে শুরু করে, মোট পদ্ধতি =iপয়েন্ট এবং বাকিn-i-1পয়েন্টের পদ্ধতির গুণফল।তাই
total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j])।লুপ শেষে
total_cuts[total_points]-এ মোট পদ্ধতি থাকবে।total_cuts[total_points]রিটার্ন করুন ফলাফল হিসেবে।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int divide_circle(int N) {
int total_points = 2 * N;
int total_cuts[total_points + 1] = { 0 };
total_cuts[0] = 1;
total_cuts[2] = 1;
for (int i = 4; i <= total_points; i += 2) {
for (int j = 0; j < i-1; j += 2) {
total_cuts[i] += (total_cuts[j] * total_cuts[i-2-j]);
}
}
return total_cuts[total_points];
}
int main() {
int N = 3;
cout << "N নন-ইন্টারসেক্টিং চর্ড দিয়ে সার্কেল ভাগ করার পদ্ধতির সংখ্যা: " << divide_circle(N);
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:
N নন-ইন্টারসেক্টিং চর্ড দিয়ে সার্কেল ভাগ করার পদ্ধতির সংখ্যা: 5
