यह देखते हुए कि यदि प्रत्येक रेखा खंड को एक समांतर चतुर्भुज में अधिक से अधिक उपयोग किया जा सकता है, तो दिए गए N संख्या रेखाखंडों का उपयोग करके बनाए जा सकने वाले समांतर चतुर्भुजों की अधिकतम संख्या ज्ञात करना है।
आइए अब एक उदाहरण का उपयोग करके समझते हैं कि हमें क्या करना है -
इनपुट - Arr[] ={8, 3, 1, 3, 8, 7, 1, 3, 5, 3}
आउटपुट -2
स्पष्टीकरण - ऊपर दिए गए रेखाखंडों से, दो समांतर चतुर्भुज जो क्रमशः 8, 1, 8, 1 और 3, 3, 3, 3 भुजाओं वाले बन सकते हैं।
इनपुट − Arr[] ={7, 9, 9, 7}
आउटपुट - 1
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
जितने समांतर चतुर्भुज बनाए जा सकते हैं, वे होंगे =समांतर चतुर्भुज जो 4 समान या समान भुजाओं के साथ बनाए जा सकते हैं और समांतर चतुर्भुज जो 2 समान भुजाओं का उपयोग करके बनाए जा सकते हैं।
-
फ़ंक्शन MaxParr() में, एक वैरिएबल L =Arr[0] को इनिशियलाइज़ करें, जिसका उपयोग उस सरणी के आकार के रूप में किया जाएगा जिसका उपयोग लाइन सेगमेंट की आवृत्तियों को संग्रहीत करने के लिए किया जाएगा।
-
i=1 से i
L), और if स्टेटमेंट के अंदर L=Arr[i] डालें। लूप के बाहर L का आकार 1 से बढ़ाएं। -
फिर आवृत्ति सरणी int Freq[L] ={0} प्रारंभ करें। i=0 से i
-
समांतर चतुर्भुज की अंतिम गणना को संग्रहीत करने के लिए प्रारंभिक गणना =0 प्रकार int।
-
i=0 से i
-
2 समान पक्षों का उपयोग करके बनाए जा सकने वाले समांतर चतुर्भुजों की संख्या को संग्रहीत करने के लिए बाएं =0 प्रकार int को प्रारंभ करें।
-
अंत में i=0 से i
=2) और यदि ऐसा है तो बाईं ओर 1 जोड़ें। -
काउंट+=लेफ्ट/2 और रिटर्न काउंट लगाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int MaxParr(int N, int Arr[]){
//Finding length of frequency array
int L = Arr[0];
for (int i = 1; i < N; i++){
if (Arr[i] > L)
L = Arr[i];
}
L = L + 1;
int Freq[L] = {0};
for (int i = 0; i < N; i++){
//Increasing occurrence of each line segment
Freq[Arr[i]] += 1;
}
// To store the number of parallelograms
int count = 0;
for (int i = 0; i < L; i++){
/*parallelograms that can be made using 4 same sides*/
count += int(Freq[i] / 4);
Freq[i] = Freq[i] % 4;
}
int left = 0;
for (int i = 0; i < L; i++){
//Counting segments with 2 or more occurrences left
if (Freq[i] >= 2)
left += 1;
}
/*Adding parallelograms that can be formed using using 2 similar sides into the final count*/
count += left / 2;
return count;
}
int main(){
int N = 10;
int Arr[] = { 8, 3, 1, 3, 8, 7, 1, 3, 5, 3};
cout<< MaxParr(N, Arr);
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो हमें निम्न आउटपुट मिलेगा -
2