दिए गए कार्य को देखते हुए किसी दिए गए पूर्णांक N के साथ एक पेड़ का निर्माण करना है, ताकि सभी क्रमित जोड़े (x,y) के लिए डिग्री (x) * डिग्री (y) का योग अधिकतम हो और x, y के बराबर नहीं है।
इनपुट −N=5
आउटपुट -50
स्पष्टीकरण
1 \ 2 \ 3 \ 4 \ 5 Degree of 1st node = 1 Degree of 2nd node = 2 Degree of 3rd node = 2 Degree of 4th node = 2 Degree of 5th node = 1
सभी क्रमित युग्मों के लिए सभी अंशों का गुणनफल (x, y) -
1st node = 1*2 + 1*2 + 1*2 + 1*1 = 7 2nd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 3rd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 4th node = 2*1 + 2*2 + 2*2 + 2*1 = 12 5th node = 1*2 + 1*2 + 1*2 + 1*1 = 7 Total sum = 50
इनपुट −N=7
आउटपुट −122
निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है
-
एक पेड़ में सभी नोड्स की डिग्री का योग है - (2 * एन) - 2. यहां एन =पेड़ में नोड्स की संख्या। योग को अधिकतम करने के लिए, लीफ नोड्स की संख्या को कम करना होगा।
-
मैक्स () फ़ंक्शन के अंदर int sum=0 प्रारंभ करें और x=1 और y=1 शर्तों वाले x
-
नेस्टेड लूप के अंदर पहले जांचें कि क्या (x ==y), यदि ऐसा है तो जारी रखें; बयान
-
अन्यथा इंट डिग्री =2 को इनिशियलाइज़ करें और if स्टेटमेंट का उपयोग करके जांचें कि क्या (x ==1 || x ==n)। अगर ऐसा है तो डिग्री एक्स =1 डालें। फिर int Degree=2 इनिशियलाइज़ करें और वेरिएबल y के लिए भी ऐसा ही करें
-
अंत में, लूप्स को बंद करने से पहले, सम वेरिएबल को लिखकर अपडेट करें - sum =(डिग्रीX + DegreeY)
उदाहरण
#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;
//Initializing degree for node x to 2
int degreeX = 2;
//If x is the leaf node or the root node
if (x == 1 || x == N)
degreeX = 1;
//Initializing degree for node y to 2
int degreeY = 2;
//If y is the leaf node or the root node
if (y == 1 || y == N)
degreeY = 1;
//Updating sum
sum += (degreeX * degreeY);
}
}
return sum;
}
//Main function
int main(){
int N = 5;
cout << Max(N);
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो हमें निम्न आउटपुट मिलेगा -
50