सी ++ में एन गैर-अंतर्विभाजक जीवाओं का उपयोग करके सर्कल को विभाजित करने के तरीकों की गणना करें

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

कुल 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 लें।
फंक्शन डिवाइड_सर्कल (इंट एन) नंबर लेता है और एन नॉन-इंटरसेक्टिंग कॉर्ड्स का उपयोग करके सर्कल को विभाजित करने के तरीकों की गिनती देता है
अंकों की कुल संख्या कुल_अंकों के रूप में 2*N होगी।
तरीकों की संख्या को संग्रहीत करते हुए एक सरणी Total_cuts[] लें।
0 या 2 अंक के लिए Total_cuts[0], total_cuts[2] को 1 से प्रारंभ करने का केवल 1 तरीका होगा।
अंक =4 से शुरू होने वाले अन्य सभी बिंदुओं के लिए, कुल तरीके अंक i और शेष n−i−1 अंक वाले तरीके होंगे।
तो Total_cuts[i] +=(total_cuts[j] * Total_cuts[i−2−j])
लें
अंत में हमारे पास टोटल_कट [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<<"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