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

C++ प्रोग्राम में n सरणियों से बढ़ते क्रम के तत्वों का अधिकतम योग


इस समस्या में, हमें n×m आकार का एक 2-D मैट्रिक्स दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो n सरणियों से बढ़ते क्रम के तत्वों का अधिकतम योग ढूंढे।

प्रोग्राम विवरण

यहां, हमें प्रत्येक पंक्ति से एक तत्व लेकर तत्वों का अधिकतम योग ढूंढना है ताकि iवीं पंक्ति का तत्व (i+1)वीं पंक्ति के तत्व से कम हो। और इसी तरह आगे। यदि ऐसा कोई योग संभव नहीं है, तो -1 वापस करें जो दर्शाता है कि कोई परिणाम संभव नहीं है।

उदाहरण

इनपुट

mat[][] = { {4, 5, 1, 3, 6}, {5, 9, 2, 7, 12}, {13, 1, 3, 6, 8}, {10, 5, 7, 2, 4} }

आउटपुट

31

व्याख्या

मैट्रिक्स से तत्व लेकर अधिकतम योग बनाना: 6 + 7 + 8 + 10 = 31
सरणी 1 से 6, अधिकतम मान। 
सरणी 2 से 7, 12 (अधिकतम मान) चुनने से समाधान नहीं मिलता। 
सरणी 3 से 8, 13 (अधिकतम मान) चुनने से समाधान नहीं मिलता। 
सरणी 4 से 10, अधिकतम मान।

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

समस्या का एक समाधान सरणियों की सरणी की अंतिम सरणी से एक तत्व चुनकर और फिर ऊपर जाते हुए दिए गए तत्व से छोटे सबसे बड़े संभावित तत्व को चुनना है।

अब, इस समाधान का उपयोग करके, हमारे पास एक मामला है जब iवीं सरणी (पंक्ति) में कोई तत्व नहीं है जो (i+1)वीं सरणी (पंक्ति) के तत्व से छोटा हो। यहां, हम -1 वापस करेंगे।

सरणी को क्रमबद्ध करना हमारे समाधान की दक्षता के लिए एक अच्छा सहायक हो सकता है। यदि हम बढ़ते क्रम में क्रमबद्ध करते हैं, तो सबसे बड़ा तत्व सूचकांक m-1 पर होगा, और अगला छोटा होगा। इसलिए, शर्त को पूरा करने वाले सबसे बड़े तत्व को ढूंढना आसान है।

एल्गोरिदम

आरंभीकरण maxSum = 0, currMax

चरण 1 -

सरणियों की सरणी की प्रत्येक सरणी को क्रमबद्ध करें (प्रत्येक में तत्व बढ़ते क्रम में होंगे)।

चरण 2 -

currMax = mat[n-1][m-1], अंतिम पंक्ति का अंतिम तत्व। maxSum अपडेट करें, maxSum = currMax।

चरण 3 -

मैट्रिक्स को पंक्तिवार लूप करें, i = n-2 से 0 तक।

चरण 3.1 -

mat[i][] में currMax से छोटे अधिकतम तत्व को सूचकांक j पर ढूंढें।

चरण 3.2 -

यदि j < 0, यानी कोई मान नहीं मिला। Return -1।

चरण 3.3 -

currMax अपडेट करें। currMax = mat[i][j]।

चरण 3.4 -

maxSum अपडेट करें, maxSum = currMax।

चरण 4 -

maxSum वापस करें।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

#include <bits/stdc++.h> 
#define M 5 
using namespace std; 

int calcMaxSumMat(int mat[][M], int n) { 
    for (int i = 0; i < n; i++) 
        sort(mat[i], mat[i] + M); 
    
    int maxSum = mat[n - 1][M - 1]; 
    int currMax = mat[n - 1][M - 1]; 
    int j; 
    
    for (int i = n - 2; i >= 0; i--) { 
        for (j = M - 1; j >= 0; j--) { 
            if (mat[i][j] < currMax) { 
                currMax = mat[i][j]; 
                maxSum += currMax; 
                break; 
            } 
        } 
        if (j == -1) 
            return 0; 
    } 
    return maxSum; 
} 

int main() { 
    int mat[][M] = { 
        {4, 5, 1, 3, 6}, 
        {5, 9, 2, 7, 12}, 
        {12, 1, 3, 6, 8}, 
        {10, 5, 7, 2, 4} 
    }; 
    int n = sizeof(mat) / sizeof(mat[0]); 
    cout<<"The maximum sum of increasing order elements from n arrays is "<<calcMaxSumMat(mat, n); 
    return 0; 
}

आउटपुट

The maximum sum of increasing order elements from n arrays is 31
  1. - तीन ऐरे से अधिकतम योग जहाँ लगातार एक ही ऐरे से तत्व चुनने की अनुमति नहीं - C++

    इस समस्या में, हमें समान आकार N के तीन ऐरे arr1[], arr2[], और arr3[] दिए गए हैं। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में तीन ऐरे से अधिकतम योग ढूंढे जहाँ लगातार एक ही ऐरे से तत्व चुनने की अनुमति नहीं है।समस्या विवरणहम N तत्वों को चुनकर अधिकतम योग ढूंढेंगे। i-वां तत्व i-वें इंडेक्स के तत्व से चु

  1. - C++ में दो दिए गए ऐरे से क्रम बनाए रखते हुए अधिकतम ऐरे बनाना

    समस्या कथन दो समान आकार के ऐरे A[] और B[] दिए गए हैं। कार्य समान आकार का तीसरा ऐरे बनाना है। परिणाम ऐरे में दोनों ऐरे से अधिकतम n तत्व होने चाहिए। इसमें A[] के चुने हुए तत्व पहले होने चाहिए, फिर B[] के चुने हुए तत्व उसी क्रम में जैसे वे मूल ऐरे में दिखाई देते हैं। यदि सामान्य तत्व हैं, तो res[] में

  1. - Python प्रोग्राम - बढ़ते क्रम में अंकों वाले तत्वों को सूची से निकालना

    जब बढ़ते क्रम में अंकों वाले तत्वों को सूची से निकालना आवश्यक हो, तो एक साधारण पुनरावृत्ति, एक फ्लैग मान और str विधि का उपयोग किया जाता है। नीचे इसका प्रदर्शन दिया गया है: उदाहरण my_list = [4578, 7327, 113, 3467, 1858] print(The list is :) print(my_list) my_result = [] for element in my_list: