모든 순서 쌍(x,y)에 대한 차수(x) * 차수(y)의 합이 최대가 되도록 주어진 정수 N으로 트리를 구성하는 작업이 주어지면 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 * N) – 2입니다. 여기서 N=트리의 노드 수입니다. 합을 최대화하려면 리프 노드의 수를 최소화해야 합니다.
-
내부 Max() 함수는 int sum=0을 초기화하고 x
조건을 갖는 x=1 및 y=1을 초기화하는 중첩 루프를 생성합니다. -
중첩 루프 내에서 먼저 if(x==y)를 확인하고, 그렇다면 계속을 추가하십시오. 성명서
-
그렇지 않으면 int degree=2를 초기화하고 if 문을 사용하여 if(x==1 || x==n)을 확인합니다. 그렇다면 degreeX=1을 입력하십시오. 그런 다음 int degree=2를 초기화하고 변수 y
에 대해 동일한 작업을 수행합니다. -
마지막으로 루프를 닫기 전에 − sum =(degreeX + degreeY)
를 작성하여 sum 변수를 업데이트합니다.
예시
#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