Được giao nhiệm vụ là xây dựng một cây với số nguyên N cho trước sao cho tổng bậc (x) * độ (y) cho tất cả các cặp có thứ tự (x, y) là lớn nhất và x không bằng y.
Đầu vào −N =5
Đầu ra −50
Giải thích
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
Sản phẩm của tất cả các độ cho tất cả các cặp đã đặt hàng (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
Đầu vào −N =7
Đầu ra −122
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tổng bậc của tất cả các nút trong cây là - (2 * N) - 2. Ở đây N =số nút trong cây. Để có tổng lớn nhất, số nút lá phải được giảm thiểu.
-
Bên trong hàm Max () khởi tạo int sum =0 và tạo các vòng lồng nhau khởi tạo x =1 và y =1 với các điều kiện x
-
Bên trong các vòng lặp lồng nhau, trước tiên hãy kiểm tra if (x ==y), nếu vậy thì thêm continue; tuyên bố
-
Khác khởi tạo int Deg =2 và sử dụng câu lệnh if kiểm tra if (x ==1 || x ==n). Nếu vậy thì đặt độX =1. Sau đó khởi tạo int Deg =2 và thực hiện tương tự đối với biến y
-
Cuối cùng, trước khi đóng các vòng lặp, hãy cập nhật biến tổng bằng cách viết - sum =(độX + độY)
Ví dụ
#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);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
50