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

C++ में सरणी को सॉर्ट करने के लिए न्यूनतम "मूव-टू-फ्रंट" चालों की गणना करें


हमें 1 से n के बीच की संख्याओं की एक सरणी दी गई है। लक्ष्य यहां दी गई सरणी को सॉर्ट करने के लिए आवश्यक 'मूव टू फ्रंट' ऑपरेशन की संख्या ढूंढना है। सरणी में कोई पुनरावृत्ति नहीं है। 'मूव टू फ्रंट' ऑपरेशन एक तत्व को चुनता है और उसे पहली स्थिति पर रखता है, यहां इंडेक्स 0 पर।

हम सरणी को अंत से पार करेंगे, यदि तत्व सही स्थिति पर है तो कोई मूव नहीं अन्यथा मूव आवश्यक है। 1 से n तक के तत्वों के लिए, सरणी में तत्व arr[i] की सही स्थिति इंडेक्स i+1 पर होनी चाहिए। arr[0] 1 होना चाहिए, arr[1] 2 होना चाहिए और...arr[n-1] n होना चाहिए।

इनपुट

Arr[]= { 4,3,2,1 }

आउटपुट

न्यूनतम मूव-टू-फ्रंट ऑपरेशन: 3

व्याख्या

3 खींचें, 3,4,2,1 count=1 2 खींचें, 2,3,4,1 count=2 1 खींचें, 1,2,3,4 count=3

इनपुट

Arr[]= { 6,1,2,5,4,3 }

आउटपुट

न्यूनतम मूव-टू-फ्रंट ऑपरेशन: 5

व्याख्या

5 खींचें, 5,6,1,2,4,3 count=1 4 खींचें, 4,5,6,1,2,3 count=2 3 खींचें, ,4,5,6,1,2 count=3 2 खींचें, 2,3,4,5,6,1 count=4 1 खींचें, 1,2,3,4,5,6 count=5

प्रयुक्त दृष्टिकोण

  • पूर्णांक सरणी Arr[] संख्याओं 1 से n को संग्रहीत करती है।
  • पूर्णांक चर size सरणी Arr[] की लंबाई संग्रहीत करता है।
  • फ़ंक्शन movetoFront(int arr[], int n) एक सरणी और इसकी लंबाई को इनपुट के रूप में लेता है और दी गई सरणी को सॉर्ट करने के लिए आवश्यक न्यूनतम 'मूव-टू-फ्रंट' ऑपरेशन की संख्या लौटाता है।
  • Count चर को सरणी के आकार के साथ आरंभ किया जाता है क्योंकि घटते क्रम की सरणी के मामले में सभी तत्वों को मूव किया जा सकता है।
  • अंतिम इंडेक्स से शुरू करके सामने की ओर पार करें, यदि तत्व का मान count के समान है, (1 से n के बीच सॉर्टेड तत्वों के लिए, n अंतिम है, n-1 दूसरा अंतिम है और इसी तरह) तो count घटाएं क्योंकि वह तत्व सही स्थिति पर है।
  • इस तरह लूप के अंत में, count में वांछित परिणाम होता है।

उदाहरण कोड

#include <bits/stdc++.h> using namespace std; // सरणी को बढ़ते क्रम में व्यवस्थित करने के लिए न्यूनतम चालों की गणना करें int movetoFront(int arr[], int n){ //count लें जैसे सभी तत्व सही ढंग से रखे गए हैं int count = n; // सरणी को अंत से पार करें for (int i=n-1; i >= 0; i--){ // यदि वर्तमान आइटम अपनी सही स्थिति पर है, //count घटाएं //रेंज 1 से n है इसलिए हर arr[i] का मान i+1 होना चाहिए //1 इंडेक्स 0 पर, 2 इंडेक्स 1 पर........ if (arr[i] == count) count--; } return count; } int main(){ int Arr[] = {5, 3, 4, 7, 2, 6, 1}; int size = 7; cout <<"सरणी को सॉर्ट करने के लिए न्यूनतम 'मूव-टू-फ्रंट': "<< movetoFront(Arr, size); return 0; }

आउटपुट

सरणी को सॉर्ट करने के लिए न्यूनतम 'मूव-टू-फ्रंट': 6

  1. C++ में न्यूनतम नाइट मूव्स C++ में न्यूनतम नाइट मूव्स

    मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [0, 0] स्क्वायर पर एक नाइट है। नाइट के 8 संभावित मूव्स होते हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक मूव कार्डिनल डायरेक्शन में दो स्क्वायर, फिर ऑर्थोगोनल डायरेक्शन में एक स्क्वायर होता है। ह

  1. - C++ में सरणी पर ऑपरेशन करके सभी तत्वों को 0 बनाने के लिए न्यूनतम ऑपरेशन

    समस्या कथन आकार N की एक सरणी दी गई है और प्रत्येक तत्व या तो 1 या 0 है। सभी तत्वों को शून्य में बदलने के लिए किए जाने वाले न्यूनतम ऑपरेशन की गणना करें। कोई निम्न ऑपरेशन कर सकता है: यदि कोई तत्व 1 है, तो आप उसका मान 0 के बराबर बदल सकते हैं, तब: यदि अगला लगातार तत्व 1 है, तो यह स्वचालित रूप से 0

  1. - C++ में सेट बिट्स की संख्या के अनुसार ऐरे सॉर्ट करें

    यहां हम सेट-बिट्स के आधार पर ऐरे को सॉर्ट करने की एक दिलचस्प समस्या देखेंगे। जब ऐरे में किसी एलिमेंट में अधिक सेट-बिट्स होते हैं, तो उसे उस एलिमेंट से पहले रखा जाएगा जिसमें कम सेट बिट्स होते हैं। मान लीजिए कुछ नंबर्स हैं 12, 15, 7। तो सेट बिट्स मूल रूप से उनके बाइनरी प्रतिनिधित्व में 1s की संख्या है