C++에서 가중치가 2의 거듭제곱인 주어진 트리의 노드를 셉니다.

노드의 가중치가 있는 이진 트리가 제공됩니다. 목표는 2의 거듭제곱이 되는 가중치를 갖는 노드의 수를 찾는 것입니다. 가중치가 32이면 25이므로 이 노드가 계산됩니다.

예를 들어

입력

값을 입력한 후 생성될 트리는 다음과 같습니다. -

출력

Count the nodes in the given tree whose weight is a power of two are: 3

설명

we are given with the tree node and the weights associated with each
node. Now we calculate the power of each and every weight and check whether it can
be expressed as power of 2 or not.

입력

값을 입력한 후 생성될 트리는 다음과 같습니다. -

출력

Count the nodes in the given tree whose weight is a power of two are: 3

설명

we are given with the tree node and the weights associated with each
node. Now we calculate the digit sum of each and every weight and check whether it's
odd or not.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -

이 접근 방식에서는 트리 그래프에 DFS를 적용하여 트리를 탐색하고 노드 가중치가 2의 거듭제곱인지 확인합니다. 이를 위해 두 벡터 Node_Weight(100) 및 edge_graph[100]를 사용합니다.

• 노드의 가중치로 Node_Weight[]를 초기화합니다.

• 벡터 edge_graph를 사용하여 나무를 만듭니다.

• 전역 변수 합계를 가져와 0으로 초기화합니다.

• power_two(int node, int root) 함수는 트리의 노드와 루트 노드를 가져와서 가중치가 2의 거듭제곱인 주어진 트리의 노드 수를 반환합니다.

• 가져오기 세트 =Node_Weight[노드];

• set &&(!(set &(set − 1)))가 true를 반환하면 2의 거듭제곱(비트 AND 및 부정)

• 증분의 거듭제곱은 2의 거듭제곱인 값을 가집니다.

• for 루프를 사용하여 벡터 edge_graph[노드]에서 트리를 탐색합니다.

• 벡터의 다음 노드에 대해 power_two(it, node)를 호출합니다.

• 모든 함수의 끝에서 우리는 2의 거듭제곱 값을 갖는 가중치를 갖는 노드 수만큼 거듭제곱을 갖게 됩니다.

예

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int powers = 0;
void power_two(int node, int root){
   int set = Node_Weight[node];
   if(set && (!(set & (set − 1)))){
      powers++;
   }
   for(int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      power_two(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 8;
   Node_Weight[1] = 100;
   Node_Weight[4] = 211;
   Node_Weight[3] = 16;
   Node_Weight[8] = 7171;
   Node_Weight[9] = 32;
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   power_two(2, 2);
   cout<<"Count the nodes in the given tree whose weight is a power of two are: "<<powers;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count the nodes in the given tree whose weight is a power of two are: 3