C++ में अधिकतम औसत मान वाला पथ

इस समस्या में एक 2D मैट्रिक्स दिया गया है, और हमें अधिकतम औसत मान वाले पथ खोजने हैं। पथ के लिए, हमारा स्रोत सबसे ऊपर बायां सेल है, और गंतव्य सबसे नीचे दायां सेल है, उदाहरण के लिए -

इनपुट: मैट्रिक्स = [1, 2, 3 4, 5, 6 7, 8, 9] आउटपुट: 5.8 अधिकतम औसत वाला पथ है, 1 -> 4 -> 7 -> 8 -> 9 पथ का योग 29 है और औसत 29/5 = 5.8 है

इस समस्या में, हमें केवल दाएं या नीचे जाने की अनुमति है। यह हमारी समस्या को आसान बनाता है क्योंकि हम जानते हैं कि हमें दाएं जाने के लिए N-1 चालें और नीचे जाने के लिए N-1 चालें चाहिए अपने गंतव्य तक पहुंचने के लिए। यह सबसे छोटा वैध पथ है, इसलिए हम इन अवलोकनों द्वारा अपना दृष्टिकोण विकसित करेंगे।

समाधान खोजने का दृष्टिकोण

इस दृष्टिकोण में, हमें अधिकतम पथ योग की गणना करने के लिए डायनामिक प्रोग्रामिंग लागू करने की आवश्यकता है क्योंकि हर निश्चित है।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

 #include <bits/stdc++.h> using namespace std; int maximumPathSum(int cost[][3], int n){ // हमारा फंक्शन जो अधिकतम औसत लौटाता है     int dp[n+1][n+1];     dp[0][0] = cost[0][0];     for (int i = 1; i < n; i++) // हमारे dp मैट्रिक्स के पहले कॉलम को इनिशियलाइज़ करना         dp[i][0] = dp[i-1][0] + cost[i][0];     for (int j = 1; j < n; j++) // हमारे dp मैट्रिक्स की पहली पंक्ति को इनिशियलाइज़ करना         dp[0][j] = dp[0][j-1] + cost[0][j];     for (int i = 1; i < n; i++) // हमारे मैट्रिक्स के बाकी हिस्से का निर्माण         for (int j = 1; j <= n; j++)             dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + cost[i][j];     return dp[n-1][n-1]; // अब हम अधिकतम पथ योग को चालों की संख्या से विभाजित करते हैं } int main(){    int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};// दी गई ग्रिड    int n = 3; // हमारे मैट्रिक्स का क्रम    printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));    return 0; }

आउटपुट

5.8

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हमने देखा कि हम जो अधिकतम चालें लेते हैं वे (2*n) - 1 के बराबर हैं, जहां n हमारी लागत मैट्रिक्स का क्रम है अब चूंकि हमारे पास एक निश्चित हर है। इसलिए, हमें अधिकतम पथ योग की गणना करने की आवश्यकता है। अब, यह क्लासिक dp समस्याओं में से एक है, और हम इसे उसी का उपयोग करके हल करते हैं, और फिर हम अपना परिणाम प्रिंट करते हैं।

निष्कर्ष

इस ट्यूटोरियल में, हम अधिकतम औसत मान वाले पथ की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिससे हमने इस समस्या को हल किया। हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।