C++ में N गैर-प्रतिच्छेदी जीवा का उपयोग करके वृत्त को विभाजित करने के तरीकों की गिनती

समस्या विवरण

एक पूर्णांक N इनपुट के रूप में दिया गया है जो 2*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

आउटपुट

वृत्त को विभाजित करने के तरीकों की संख्या: 14

व्याख्या

कुल 8 बिंदु होंगे जिनके बीच हम जीवा खींच सकते हैं। पहली जीवा खींचने के बाद, बाकी बिंदु दो सेट में विभाजित हो जाएंगे। सेट 1 और सेट 2 के बिंदुओं के बीच कोई जीवा नहीं खींची जा सकती क्योंकि वे पहली जीवा को प्रतिच्छेद करेंगी।

इनपुट

N=6

आउटपुट

वृत्त को विभाजित करने के तरीकों की संख्या: 132

व्याख्या

कुल 12 बिंदु होंगे जिनके बीच हम जीवा खींच सकते हैं। पहली जीवा खींचने के बाद, बाकी बिंदु दो सेट में विभाजित हो जाएंगे। सेट 1 और सेट 2 के बिंदुओं के बीच कोई जीवा नहीं खींची जा सकती क्योंकि वे पहली जीवा को प्रतिच्छेद करेंगी।

दृष्टिकोण

इस दृष्टिकोण में हम पिछली गिनती का उपयोग करके तरीकों की गिनती करेंगे। यदि हम किन्हीं 2 बिंदुओं के बीच कोई जीवा खींचते हैं, तो बाकी बिंदु दो सेट set1 और set2 में विभाजित हो जाएंगे, यदि हम इन दो सेटों में बिंदुओं के बीच कोई जीवा खींचते हैं तो वे पहली जीवा को प्रतिच्छेद करेंगे।

एल्गोरिदम चरण

एक पूर्णांक N इनपुट के रूप में लें।
फंक्शन divide_circle(int N) संख्या लेता है और N गैर-प्रतिच्छेदी जीवा का उपयोग करके वृत्त को विभाजित करने के तरीकों की संख्या लौटाता है।
कुल बिंदुओं की संख्या 2*N होगी total_points के रूप में।
तरीकों की गिनती संग्रहीत करने के लिए सरणी total_cuts[] लें।
0 या 2 बिंदुओं के लिए केवल 1 तरीका होगा, total_cuts[0], total_cuts[2] को 1 से प्रारंभ करें।
बाकी सभी बिंदुओं के लिए 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] लौटाएं।

C++ कोड उदाहरण

#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 << "वृत्त को विभाजित करने के तरीकों की संख्या: " << divide_circle(N);
    return 0;
}

आउटपुट

वृत्त को विभाजित करने के तरीकों की संख्या: 5