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

C++ में राइट नंबर ट्रायंगल में एक पथ का अधिकतम योग (Maximum sum of a path in a Right Number Triangle)


समस्या कथन

संख्याओं का एक राइट ट्रायंगल दिया गया है, उन संख्याओं के योग का अधिकतम मान ढूंढें जो शीर्ष से आधार की ओर शुरू होने वाले पथों पर दिखाई देते हैं, ताकि प्रत्येक पथ पर अगली संख्या सीधे नीचे या नीचे-और-एक-स्थान-दाएं स्थित हो।

उदाहरण

यदि दिया गया इनपुट है:
3
4 5
1 10 7
तो अधिकतम योग 18 है (3 + 5 + 10)।

एल्गोरिदम

विचार अंतिम पंक्ति के प्रत्येक सेल पर समाप्त होने वाले सबसे बड़े योग को ढूंढना है और इन योगों का अधिकतम वापस करना है।

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

चूंकि ओवरलैपिंग उप-समस्याएं हैं, हम डायनामिक प्रोग्रामिंग का उपयोग करके अंतिम पंक्ति के विशेष सेल पर समाप्त होने वाले अधिकतम योग को ढूंढते हैं।

उदाहरण

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

int maxSum(int tringle[][3], int n){
    if (n > 1) {
        tringle[1][1] = tringle[1][1] + tringle[0][0];
        tringle[1][0] = tringle[1][0] + tringle[0][0];
    }
    for(int i = 2; i < n; i++) {
        tringle[i][0] = tringle[i][0] + tringle[i-1][0];
        tringle[i][i] = tringle[i][i] + tringle[i-1][i-1];
        for (int j = 1; j < i; j++){
            if (tringle[i][j] + tringle[i-1][j-1] >= tringle[i][j] + tringle[i-1][j]) {
                tringle[i][j] = tringle[i][j] + tringle[i-1][j-1];
            } else {
                tringle[i][j] = tringle[i][j] + tringle[i-1][j];
            }
        }
    }
    int max = tringle[n - 1][0];
    for(int i = 1; i < n; i++) {
        if(max < tringle[n-1][i]) {
            max = tringle[n-1][i];
        }
    }
    return max;
}

int main(){
    int tringle[3][3] = {
        {3},
        {4,5},
        {1,10,7}
    };
    cout << "अधिकतम योग = " << maxSum(tringle, 3) << endl;
    return 0;
}

आउटपुट

अधिकतम योग = 18
  1. C++ में अधिकतम मोड़ों वाला पथ लंबाई C++ में अधिकतम मोड़ों वाला पथ लंबाई

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

  1. C++ में समकोण समद्विबाहु त्रिभुज में फिट होने वाले वर्गों की अधिकतम संख्या C++ में समकोण समद्विबाहु त्रिभुज में फिट होने वाले वर्गों की अधिकतम संख्या

    दिया गया कार्य भुजा a वाले वर्गों की अधिकतम संख्या ढूंढना है जो आधार s वाले दिए गए समकोण समद्विबाहु त्रिभुज (An isosceles triangle has at least 2 equal sides) के अंदर फिट हो सकते हैं। उदाहरण इनपुट s=5, a=1 आउटपुट 10 व्याख्या - आधार में वर्गों की संख्या की गणना s को a से विभाजित करके और 1 घटाकर क

  1. C++ में बाइनरी ट्री में अधिकतम पथ योग C++ में बाइनरी ट्री में अधिकतम पथ योग

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड एक मान रखता है। हमारा कार्य बाइनरी ट्री के दो पत्तों के बीच अधिकतम पथ योग ढूंढने के लिए एक प्रोग्राम बनाना है। यहां, हमें एक पत्ते नोड से दूसरे पत्ते नोड तक का पथ ढूंढना है जो मानों का अधिकतम योग प्रदान करेगा। यह अधिकतम योग पथ रूट न