นับโหนดที่มีน้ำหนักเป็นกำลังสองสมบูรณ์ใน C++

กำหนดไบนารีทรีที่มีน้ำหนักของโหนด เป้าหมายคือการหาจำนวนโหนดที่มีน้ำหนักเพื่อให้เป็นจำนวนเต็มกำลังสอง หากน้ำหนักเท่ากับ 36 ก็จะเป็น 62 ดังนั้นโหนดนี้จะถูกนับ

ตัวอย่าง

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

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

คำอธิบาย

เราได้รับกับโหนดต้นไม้และน้ำหนักที่เกี่ยวข้องกับแต่ละโหนด ตอนนี้เราตรวจสอบว่าตัวเลขของโหนดเป็นกำลังสองสมบูรณ์หรือไม่

อินพุต

ต้นไม้ที่จะถูกสร้างขึ้นหลังจากป้อนค่าจะได้รับด้านล่าง -

ผลลัพธ์

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

คำอธิบาย

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.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะใช้ DFS กับกราฟของต้นไม้เพื่อข้ามผ่าน และตรวจสอบว่าน้ำหนักของโหนดเป็นกำลังสองสมบูรณ์หรือไม่ ใช้เวกเตอร์ Node_Weight(100) และ edge_graph[100] สองตัวเพื่อการนี้

• เริ่มต้น Node_Weight[] ด้วยน้ำหนักของโหนด

• สร้างต้นไม้โดยใช้ vector edge_graph

• ใช้สี่เหลี่ยมตัวแปรส่วนกลางและเริ่มต้นด้วย 0

• การตรวจสอบฟังก์ชัน (int check_it) ใช้จำนวนเต็มและคืนค่า จริง หาก check_it เป็นกำลังสองสมบูรณ์

• เอาผลรวม =sqrt(check_it)

• ตอนนี้ if(floor(total) !=ceil(total)) คืนค่า true ผลรวมไม่ใช่กำลังสองสมบูรณ์ ให้คืนค่าเท็จ

• คืนค่า true มิฉะนั้น

• ฟังก์ชัน perfect_square(int node, int root) รับโหนดและโหนดรูทของต้นไม้และคืนค่าจำนวนโหนดในทรีที่กำหนดซึ่งมีน้ำหนักเป็นกำลังสองสมบูรณ์

• ถ้า if(check(Node_Weight[node])) คืนค่า true ให้เพิ่มกำลังสอง

• ต้นไม้ขวางใน vector edge_graph[node] ใช้สำหรับวนซ้ำ

• เรียก perfect_square(it, node) สำหรับโหนดถัดไปในเวกเตอร์

• ที่ส่วนท้ายของฟังก์ชันทั้งหมด เราจะมีสี่เหลี่ยมจัตุรัสเท่ากับจำนวนโหนดที่มีน้ำหนักมีค่าเป็นกำลังสองสมบูรณ์

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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