एक बाइनरी ट्री को देखते हुए इसके नोड्स के वजन के साथ। लक्ष्य उन नोड्स की संख्या का पता लगाना है जिनका वजन इस तरह है कि संख्या एक पूर्ण वर्ग है। अगर वजन 36 है तो यह 62 है इसलिए इस नोड को गिना जाएगा।
उदाहरण के लिए
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count the nodes whose weight is a perfect square are: 4
स्पष्टीकरण
हमें ट्री नोड्स और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम जांचते हैं कि नोड्स के अंक पूर्ण वर्ग हैं या नहीं।
| नोड | <थ>वजनबिल्कुल सही वर्ग | हां/नहीं | |
|---|---|---|---|
| 2 | 121 | 11*11 | हां |
| 1 | 81 | 9*9 | हां |
| 4 | 37 | प्राइम नंबर | नहीं |
| 3 | 25 | 5*5 | हां |
| 8 | 100 | 10*10 | हां |
| 9 | 701 | संभव नहीं | नहीं |
इनपुट
मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
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.
| नोड | <थ>वजन <वें शैली="">बिल्कुल सही वर्गहां/नहीं | ||
|---|---|---|---|
| 2 | 11 | संभव नहीं | नहीं |
| 1 | 16 | 4*4 | हां |
| 4 | 4 | 2*2 | हां |
| 3 | 26 | संभव नहीं | नहीं |
| 8 | 1001 | संभव नहीं | नहीं |
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम पेड़ के ग्राफ पर डीएफएस लागू करेंगे और जांचेंगे कि नोड का वजन एक पूर्ण वर्ग है या नहीं। इस उद्देश्य के लिए दो वैक्टर Node_Weight(100) और edge_graph[100] लें।
-
नोड्स के भार के साथ Node_Weight[] प्रारंभ करें।
-
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
-
एक वैश्विक चर वर्ग लें और इसे 0 से प्रारंभ करें।
-
फ़ंक्शन check(int check_it) एक पूर्णांक लेता है और अगर check_it एक पूर्ण वर्ग है, तो सही लौटाता है।
-
कुल लें =sqrt(check_it)
-
अब अगर(floor(total) !=ceil(total)) रिटर्न सही है तो टोटल एक पूर्ण वर्ग नहीं है, रिटर्न गलत है।
-
अन्यथा सही लौटें।
-
फंक्शन Perfect_square(int node, int root) एक पेड़ का एक नोड और रूट नोड लेता है और दिए गए पेड़ में नोड्स की गिनती देता है जिसका वजन एक पूर्ण वर्ग है।
-
अगर (चेक (नोड_वेट [नोड])) सही है, तो वर्ग वृद्धि करें।
-
लूप के लिए उपयोग कर वेक्टर edge_graph[नोड] में ट्रैवर्स ट्री।
-
वेक्टर में अगले नोड के लिए 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