2*N শেষ বিন্দু সহ একটি বৃত্তে একাধিক জ্যার জন্য ইনপুট হিসাবে একটি পূর্ণসংখ্যা N দেওয়া হয়েছে৷ লক্ষ্য হল সেই উপায়গুলি গণনা করা যাতে আমরা এই ধরনের জ্যা ব্যবহার করে সেই বৃত্তটিকে ভাগ করতে পারি যাতে কোনো জ্যা একে অপরের সাথে ছেদ না করে।
N=3 এর জন্য, পয়েন্ট হবে 6, 3টি জ্যা পাওয়ার 1 উপায় হল 1−2, 3−4, 5−6
অন্যান্য উপায় -
1−6, 2−5, 3−4 1−2, 3−6, 4−5 1−4, 2−3, 5−6 1−6, 2−3, 4−5
মোট ৫টি উপায়।
উদাহরণস্বরূপ
ইনপুট
N=4
আউটপুট
Count of ways to divide circle using N non-intersecting chords are: 14
ব্যাখ্যা
There will be a total 8 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.
ইনপুট
N=6
আউটপুট
Count of ways to divide circle using N non−intersecting chords are: 132
ব্যাখ্যা
There will be a total 12 points between which we can draw chords. After drawing the first chord, the rest of the points will be divided into two sets. No chord can be drawn between points from set 1 and set 2 as they will intersect with the first chord.
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা পূর্ববর্তী গণনা ব্যবহার করে উপায় গণনা করব। যদি আমরা 2 বিন্দুর মধ্যে কোনো জ্যা আঁকি, বাকি বিন্দু দুটি সেট 1 এবং সেট 2 এ বিভক্ত হবে, যদি আমরা এই দুটি সেটের বিন্দুর মধ্যে কোনো জ্যা আঁকি তাহলে তারা প্রথম জ্যাটির সাথে ছেদ করবে।
-
ইনপুট হিসাবে একটি পূর্ণসংখ্যা N নিন।
-
ফাংশন divide_circle(int N) সংখ্যা নেয় এবং N নন-ইন্টারসেক্টিং কর্ড ব্যবহার করে বৃত্তকে ভাগ করার উপায় গণনা করে
-
মোট পয়েন্টের সংখ্যা হবে 2*N মোট_পয়েন্ট হিসেবে।
-
উপায় গণনা সংরক্ষণ করে একটি অ্যারে total_cuts[] নিন।
-
0 বা 2 পয়েন্টের জন্য টোটাল_কাট[0], টোটাল_কাট[2] 1 দিয়ে আরম্ভ করার জন্য শুধুমাত্র 1 উপায় থাকবে।
-
পয়েন্ট=4 থেকে শুরু করে অন্য সব পয়েন্টের জন্য, মোট উপায় হবে পয়েন্ট i এবং বাকি n−i−1 পয়েন্ট সহ।
-
সুতরাং টোটাল_কাট নিন
-
শেষে আমাদের মোট_কাট [ মোট_পয়েন্ট ] উপায়ের মোট সংখ্যা আছে।
-
লুপের শেষে মোট_কাট [ মোট_পয়েন্ট ] ফেরত দিন।
উদাহরণ
#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<<"Count of ways to divide circle using N non−intersecting chords are:"<<divide_circle(N);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of ways to divide circle using N non-intersecting chords are: 5
