C++ में कुल n अंक के साथ m कोलिनियर वाले त्रिभुजों की संख्या

हमें दो चर n और m दिए गए हैं जो एक 2D तल पर बिंदुओं की संख्या को निरूपित करते हैं। n बिंदुओं में से, m बिंदु संरेख हैं। लक्ष्य इन n बिंदुओं का उपयोग करके बनाए जा सकने वाले त्रिभुजों की संख्या ज्ञात करना है।

समरेख बिंदु - एक ही रेखा पर स्थित बिंदु संरेख कहलाते हैं। बिंदु A और B संरेख हैं।

दिया गया n=4 (A,B,C,D ), m=2 (A,B)

त्रिभुजों की संख्या -

4 =4C₃ . में से किन्हीं तीन बिंदुओं को चुनना

लेकिन संरेख बिंदु त्रिभुज नहीं बना सकते इसलिए संभावित त्रिभुजों को हटा दें जिन्हें ऊपर गिना जाएगा =2C₃

कुल त्रिभुज =4C<उप>3 - 2सी<उप>3 =4-0 =4 (एबीसी, एसीडी, बीसीडी, एबीडी)

n और m =nC₃ . के लिए - एमसी<उप>3

आइए उदाहरणों से समझते हैं।

इनपुट - n=5, m=3

आउटपुट − m कोलीनियर वाले कुल n बिंदुओं वाले त्रिभुजों की संख्या − 9

. है

स्पष्टीकरण − कुल त्रिभुज =5C₃ - 3सी<उप>3 =10 - 1 =9

इनपुट - n=10, m=5

आउटपुट − m कोलीनियर वाले कुल n बिंदुओं वाले त्रिभुजों की संख्या − 110

. है

स्पष्टीकरण − कुल त्रिभुज =10C<उप>3 - 5सी<उप>3 =120 - 10 =110

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

हम संयोजनों की गणना करने के लिए एक पास्कल त्रिभुज बनाएंगे। प्रत्येक पंक्ति की गणना पिछली पंक्ति के स्तंभों को जोड़कर की जाती है।

कई बिंदुओं के लिए चर n और m को इनपुट के रूप में लें।
फ़ंक्शन collinear_points(int n,int m) n और m लेता है और m कोलीनियर के साथ कुल n बिंदुओं वाले त्रिभुजों की संख्या लौटाता है।
गिनती सेट करें =चेक (एन, 3) - चेक (एम, 3); (एनसी<उप>3 की गणना के लिए - एमसी<उप>3 )
फ़ंक्शन चेक (int n, int r) n और r लेता है और nC_r का मान देता है
लंबाई r+1 की एक सरणी गिरफ्तारी लें।
पूरे सरणी को 0 के मेमसेट का उपयोग करके सेट करें।
गिरफ्तारी सेट करें [0] =1.
i=0 से i<=n तक लूप के लिए दो का उपयोग करना। और j=min (i,r) से j>0 पास्कल त्रिभुज को arr[j]=arr[j]+arr[j-1] के रूप में परिकलित करें।
अंत में हम arr[r] को nC_r . के रूप में प्राप्त करेंगे . इसे वापस करें।
फ़ंक्शन चेक () के अंत के बाद। हमें त्रिभुजों की गिनती मिलेगी
परिणाम के रूप में वापसी की गिनती।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int check(int n, int r){
   int arr[r+1];
   memset(arr, 0, sizeof(arr));
   arr[0] = 1;
   for (int i = 1; i <= n; i++){
      for (int j = min(i, r); j > 0; j--){
         arr[j] = arr[j] + arr[j-1];
      }  
   }
   return arr[r];
}
int collinear_points(int n,int m){
   int count = check(n, 3) - check(m, 3);
   return count;
}
int main(){
   int n = 6, m = 2;
   cout<<"Count of triangles with total n points with m collinear are: "<< collinear_points(n, m);
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Count of triangles with total n points with m collinear are: 20