Đếm các nút có trọng lượng là một hình vuông hoàn hảo trong C ++

Cho một cây nhị phân với trọng số là các nút của nó. Mục đích là tìm số nút có trọng số sao cho số đó là một hình vuông hoàn hảo. Nếu trọng số là 36 thì nó là 62 nên nút này sẽ được tính.

Ví dụ

Đầu vào

Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới -

Đầu ra

Count the nodes whose weight is a perfect square are: 4

Giải thích

chúng ta được cung cấp với các nút cây và trọng số liên quan đến mỗi nút. Bây giờ chúng ta kiểm tra xem các chữ số của các nút có phải là hình vuông hoàn hảo hay không.

Đầu vào

Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới -

Đầu ra

Count the nodes whose weight is a perfect square are: 2

Giải thích

we are given with the tree nodes and the weights associated with each
node. Now we check whether the digits of nodes are perfect squares or not.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ áp dụng DFS trên đồ thị của cây để duyệt qua nó và kiểm tra xem trọng lượng của nút có phải là một hình vuông hoàn hảo hay không. Lấy hai vectơ Node_Weight (100) và edge_graph [100] cho mục đích này.

• Khởi tạo Node_Weight [] với trọng số của các nút.

• Tạo cây bằng cách sử dụng vector edge_graph.

• Lấy một hình vuông biến toàn cục và khởi tạo nó bằng 0.

• Kiểm tra hàm (int check_it) nhận một số nguyên và trả về true nếu check_it là một hình vuông hoàn hảo.

• Lấy tổng =sqrt (check_it)

• Bây giờ nếu (floor (total)! =Ceil (total)) trả về true thì tổng không phải là một hình vuông hoàn hảo, hãy trả về false.

• Nếu ngược lại thì trả về true.

• Hàm perfect_square (int node, int root) lấy một nút và nút gốc của cây và trả về số lượng các nút trong cây đã cho có trọng số là một hình vuông hoàn hảo.

• Nếu if (check (Node_Weight [node])) trả về true, thì bình phương tăng dần.

• Cây ngang trong vector edge_graph [node] sử dụng vòng lặp for.

• Gọi perfect_square (nó, nút) cho nút tiếp theo trong vectơ.

• Ở cuối tất cả các hàm, chúng ta sẽ có một hình vuông là số nút có trọng số có giá trị là một hình vuông hoàn hảo.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int square = 0;
bool check(int check_it){
   double total = sqrt(check_it);
   if(floor(total) != ceil(total)){
      return false;
   }
   return true;
}
void perfect_square(int node, int root){
   if(check(Node_Weight[node])){
      square++;
   }
   for (int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      perfect_square(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 121;
   Node_Weight[1] = 81;
   Node_Weight[4] = 37;
   Node_Weight[3] = 25;
   Node_Weight[8] = 100;
   Node_Weight[9] = 701;
   //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);
   perfect_square(2, 2);
   cout<<"Count the nodes whose weight is a perfect square are: "<<square;
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count the nodes whose weight is a perfect square are: 4