C++ में ट्री में किन्हीं दो शीर्षों की डिग्री के गुणनफल के योग को अधिकतम करना

दिया गया कार्य एक दिए गए पूर्णांक N के साथ एक ट्री का निर्माण करना है जैसे कि, सभी क्रमित जोड़े (x,y) के लिए degree(x) * degree(y) का योग अधिकतम हो और x, y के बराबर न हो।

इनपुट - N=5

आउटपुट - 50

व्याख्या

    1
     \
      2
       \
        3
         \
          4
           \
            5
पहले नोड की डिग्री = 1
दूसरे नोड की डिग्री = 2
तीसरे नोड की डिग्री = 2
चौथे नोड की डिग्री = 2
पांचवें नोड की डिग्री = 1

सभी क्रमित जोड़े (x, y) के लिए सभी डिग्री का गुणनफल:
पहला नोड = 1*2 + 1*2 + 1*2 + 1*1 = 7
दूसरा नोड = 2*1 + 2*2 + 2*2 + 2*1 = 12
तीसरा नोड = 2*1 + 2*2 + 2*2 + 2*1 = 12
चौथा नोड = 2*1 + 2*2 + 2*2 + 2*1 = 12
पांचवां नोड = 1*2 + 1*2 + 1*2 + 1*1 = 7
कुल योग = 50

इनपुट - N=7

आउटपुट - 122

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

ट्री में सभी नोड्स की डिग्री का योग = (2 * N) - 2। यहां N = ट्री में नोड्स की संख्या। योग को अधिकतम करने के लिए, पत्ती नोड्स की संख्या को न्यूनतम करना होगा।
Max() फंक्शन के अंदर int sum=0 आरंभ करें और x=1 और y=1 को आरंभ करके नेस्टेड लूप बनाएं जिनकी शर्तें x<=N और y<=N हों।
नेस्टेड लूप के अंदर पहले चेक करें यदि (x==y), यदि हां तो continue; स्टेटमेंट जोड़ें।
अन्यथा int degree=2 आरंभ करें और if स्टेटमेंट का उपयोग करके चेक करें यदि (x==1 || x==n)। यदि हां तो degreeX=1 रखें। फिर y वेरिएबल के लिए int degree=2 आरंभ करें और वही करें।
अंत में, लूप बंद करने से पहले, योग वेरिएबल को अपडेट करें: sum += (degreeX * degreeY)

C++ प्रोग्राम उदाहरण

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

int Max(int N) {
    int sum = 0;
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            if (x == y)
                continue;
            
            // नोड x के लिए डिग्री को 2 से आरंभ करना
            int degreeX = 2;
            // यदि x पत्ती नोड या रूट नोड है
            if (x == 1 || x == N)
                degreeX = 1;
            
            // नोड y के लिए डिग्री को 2 से आरंभ करना
            int degreeY = 2;
            // यदि y पत्ती नोड या रूट नोड है
            if (y == 1 || y == N)
                degreeY = 1;
            
            // योग अपडेट करना
            sum += (degreeX * degreeY);
        }
    }
    return sum;
}

int main() {
    int N = 5;
    cout << Max(N);
}