मैं कंप्यूटर अनुप्रयोग 2210 (डेटा संरचनाएं) अगले सेमेस्टर ले रहा हूँ और मैं गर्मियों सेमेस्टर कि ऑनलाइन पोस्ट किया जाता है के लिए होमवर्क कर रहा हूँ कम से कम। अब तक, मुझे असाइनमेंट करने में कोई समस्या नहीं है। नीचे असाइनमेंट 4 पर एक नज़र डालें, और देखें कि क्या आप मुझे इस बात का संकेत दे सकते हैं कि इसे कैसे पहुंचाया जाए। कृपया एक पूर्ण एल्गोरिदम प्रदान न करें, केवल एक दृष्टिकोण। धन्यवाद!क्रमबद्ध सरणी, जबकि "लागत"
ए 'costed तरह "एक एल्गोरिथ्म जिसमें मूल्यों का एक अनुक्रम आरोही क्रम में व्यवस्थित किया जाना चाहिए है। क्रमशः अनुक्रम एक उचित क्रम में दो मानों की स्थिति को एक दूसरे में स्थानांतरित करके किया जाता है। प्रत्येक इंटरचेंज एक लागत उत्पन्न करता है, जिसे इंटरचेंज में शामिल दो मूल्यों के योग के रूप में गणना की जाती है। कुल इस प्रकार की लागत इंटरचेंजों की लागत का योग है।
उदाहरण के लिए, मान लें कि अनुक्रम {3, 2, 1} था। इंटरचेंज से एक संभव श्रृंखला
Interchange 1: {3, 1, 2} interchange cost = 0
Interchange 2: {1, 3, 2} interchange cost = 4
Interchange 3: {1, 2, 3} interchange cost = 5,
given a total cost of 9
आप एक प्रोग्राम है जो संख्या के विशिष्ट क्रम की व्यवस्था करने के लिए कम से कम लागत निर्धारित करता है लिखने के लिए कर रहे हैं।
संपादित करें: प्रोफेसर ब्रूट फोर्सिंग की अनुमति नहीं देता है।
क्या आपको केवल आसन्न मूल्यों का आदान-प्रदान करने की अनुमति है? – Bubblewrap
नहीं, किसी भी तत्व को इंटरचेंज किया जा सकता है। – dacman
यह स्पष्ट रूप से एक अकादमिक समस्या है - वास्तविक जीवन में, यह तुलना है कि एक्सचेंजों की तुलना में बहुत अधिक लागत होती है। आम तौर पर, एक एल्गोरिदम जो किसी भी प्रकार की चालों की संख्या को कम करता है, बेहतर होता है –