Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

सी ++ में एक सरणी में क्रॉस लाइनों की गणना करना


हमें अलग-अलग तत्वों की एक सरणी दी गई है जो क्रमबद्ध नहीं हैं। लक्ष्य सरणी को क्रमबद्ध करने के बाद क्रॉस लाइनों को खोजना है। क्रॉस लाइन की गणना नीचे दर्शाए अनुसार की जाती है -

  • Arr[]={ 1,2,4,3,5 } नीचे दिखाए गए अनुसार 3 क्रॉस लाइन हैं

सी ++ में एक सरणी में क्रॉस लाइनों की गणना करना

  • एआर [] ={ 1,2,3,4,5}। कोई क्रॉस लाइन नहीं है क्योंकि सरणी पहले से ही क्रमबद्ध है।

हम सम्मिलन सॉर्ट का उपयोग करके क्रॉस लाइनों की गणना करेंगे जिसमें दाईं ओर से एक तत्व को इसके बाईं ओर सॉर्ट किए गए तत्वों में जोड़ा जाता है। हर बार जब तत्व को सॉर्ट किए गए भाग में जोड़ा जाता है, तो वृद्धि की गणना की जाती है क्योंकि यह अपनी सही स्थिति में जाता है। यह उन सभी तत्वों को पार करके गुजरेगा जो बड़े हैं।

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

इनपुट - गिरफ्तारी [] ={4,3,1,2 }

आउटपुट - सरणी में क्रॉस लाइनों की संख्या - 5

स्पष्टीकरण - रेखा 4-4 और 3-3 रेखा 1-1 और 2-2 को पार करती है। कुल 4 क्रॉस लाइन।

4-4 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 4+1=5 क्रॉस लाइन।

इनपुट - गिरफ्तारी [] ={ 0,1,5,3 }

आउटपुट - सरणी में क्रॉस लाइनों की संख्या - 1

स्पष्टीकरण - 5-5 और 3-3 दोनों एक दूसरे को एक बार पार करते हैं। कुल 1 क्रॉस लाइन।

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

  • हम एक पूर्णांक सरणी लेते हैं arr[] अलग-अलग संख्याओं के साथ आरंभ किया गया।

  • फ़ंक्शन सम्मिलन सॉर्ट (int arr [], int n) इनपुट के रूप में एक सरणी और उसकी लंबाई लेता है और सॉर्ट करने के बाद परिणाम के रूप में क्रॉस लाइनों की गिनती देता है।

  • क्रॉस लाइनों की प्रारंभिक संख्या को 0 के रूप में लें। गणना चर का उपयोग किया जाता है।

  • पहला तत्व पहले से ही क्रमबद्ध है, इसलिए दूसरे तत्व से शुरू होकर अंत तक (i=1 से i

  • अब सभी तत्वों को सही शिफ्ट करें यदि वे> आइटम और j>0 हैं। प्रत्येक पारी वेतन वृद्धि की गणना के रूप में इन सभी को आइटम द्वारा पार किया जाता है।

  • लूप के अंत में आइटम को उसकी सही स्थिति में रखें जो कि arr[j+1] है।

  • ऐसा सभी तत्वों के लिए करें और उन तत्वों को गिनें जिन्हें वे पार करते हैं।

  • संख्या के रूप में वृद्धि मूल्य। क्रॉस लाइन संभव है।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
   int count=0;
   int item;
   int j;
   for (int i = 1; i < n; i++){
      item = arr[i];
      j = i - 1;
      //insert element at correct position in sorted part, no. of elements it passes
      //from right till correct position is count of cross lines.
      while (j >= 0 && arr[j] > item){
         arr[j + 1] = arr[j];
         j = j - 1;
         count++;
      }
      arr[j + 1] = item;
   }
   return count;
}
int main(){
   int arr[] = { 4,5,3,1,2};
   int n = 5;
   cout<<"Number of cross lines: "<<insertionSort(arr, n);
   return 0;
}

आउटपुट

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

Number of cross lines: 8

  1. सी ++ स्ट्रिंग्स की सरणी

    इस खंड में हम देखेंगे कि C++ में स्ट्रिंग्स की एक सरणी को कैसे परिभाषित किया जाए। जैसा कि हम जानते हैं कि सी में कोई तार नहीं था। हमें कैरेक्टर ऐरे का उपयोग करके स्ट्रिंग्स बनाना है। इसलिए स्ट्रिंग्स की कुछ सरणी बनाने के लिए, हमें वर्णों की एक 2-आयामी सरणी बनानी होगी। प्रत्येक पंक्तियाँ उस मैट्रिक्स

  1. सी++ में छँटाई

    इस खंड में हम देखेंगे कि C++ में सॉर्टिंग एल्गोरिथम कैसे किया जाता है। एक क्रमबद्ध सरणी एक सरणी है जिसमें प्रत्येक तत्व को किसी क्रम में क्रमबद्ध किया जाता है जैसे संख्यात्मक, वर्णानुक्रम आदि। संख्यात्मक सरणी को सॉर्ट करने के लिए कई एल्गोरिदम हैं जैसे कि बबलसॉर्ट, इंसर्शन सॉर्ट, सेलेक्शन सॉर्ट, मर्ज

  1. C++ प्रोग्राम काउंटिंग सॉर्ट को लागू करने के लिए

    काउंटिंग सॉर्ट एक स्थिर छँटाई तकनीक है, जिसका उपयोग वस्तुओं को छोटी संख्याओं की कुंजियों के अनुसार क्रमबद्ध करने के लिए किया जाता है। यह उन कुंजियों की संख्या की गणना करता है जिनके प्रमुख मान समान हैं। यह छँटाई तकनीक कुशल है जब विभिन्न कुंजियों के बीच का अंतर इतना बड़ा नहीं है, अन्यथा यह स्थान की जट