Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में उन नोड्स को गिनना जिनका वजन एक परफेक्ट स्क्वायर है


नोड्स के वजन वाली एक बाइनरी ट्री दी गई है। लक्ष्य उन नोड्स की संख्या ढूंढना है जिनके वजन ऐसे हैं कि संख्या एक परफेक्ट स्क्वायर है। यदि वजन 36 है तो यह 6² है इसलिए यह नोड गिना जाएगा।

उदाहरण के लिए

इनपुट

मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

C++ में उन नोड्स को गिनना जिनका वजन एक परफेक्ट स्क्वायर है

आउटपुट

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

व्याख्या

हमें ट्री नोड्स और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम जांचते हैं कि नोड्स के अंक परफेक्ट स्क्वायर हैं या नहीं।

नोडवजनपरफेक्ट स्क्वायरहां/नहीं
212111*11हां
1819*9हां
437अभाज्य संख्यानहीं
3255*5हां
810010*10हां
9701संभव नहींनहीं

इनपुट

मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

C++ में उन नोड्स को गिनना जिनका वजन एक परफेक्ट स्क्वायर है

आउटपुट

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

व्याख्या

हमें ट्री नोड्स और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम जांचते हैं कि नोड्स के अंक परफेक्ट स्क्वायर हैं या नहीं।


नोडवजनपरफेक्ट स्क्वायरहां / नहीं
211संभव नहींनहीं
1164*4हां
442*2हां
326संभव नहींनहीं
81001संभव नहींनहीं

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:

इस दृष्टिकोण में हम ट्री के ग्राफ पर DFS लागू करेंगे इसे ट्रैवर्स करने के लिए और जांचेंगे कि क्या नोड का वजन एक परफेक्ट स्क्वायर है। इस उद्देश्य के लिए दो वेक्टर Node_Weight(100) और edge_graph[100] लें।

  • Node_Weight[] को नोड्स के वजन से इनिशियलाइज़ करें।

  • वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।

  • एक ग्लोबल वेरिएबल square लें और इसे 0 से इनिशियलाइज़ करें।

  • फ़ंक्शन check(int check_it) एक पूर्णांक लेता है और ट्रू लौटाता है यदि check_it एक परफेक्ट स्क्वायर है।

  • total = sqrt(check_it) लें।

  • अब यदि (floor(total) != ceil(total)) ट्रू लौटाता है तो total परफेक्ट स्क्वायर नहीं है, फॉल्स लौटाएं।

  • अन्यथा ट्रू लौटाएं।

  • फ़ंक्शन perfect_square(int node, int root) एक नोड और ट्री का रूट नोड लेता है और दिए गए ट्री में उन नोड्स की संख्या लौटाता है जिनका वजन एक परफेक्ट स्क्वायर है।

  • यदि if(check(Node_Weight[node])) ट्रू लौटाता है, तो square बढ़ाएं।

  • फॉर लूप का उपयोग करके वेक्टर edge_graph[node] में ट्री को ट्रैवर्स करें।

  • वेक्टर में अगले नोड के लिए perfect_square(it, node) कॉल करें।

  • सभी फ़ंक्शन के अंत में हमारे पास square उन नोड्स की संख्या के रूप में होगा जिनके वजन का मान परफेक्ट स्क्वायर है।

उदाहरण

#include <bits/stdc++.h> using namespace std; vector Node_Weight(100); vector 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

  1. C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें C++ में सर्कुलर लिंक्ड लिस्ट में नोड्स की गिनती करें

    हमें नोड्स के साथ एक सर्कुलर लिंक्ड लिस्ट दी गई है और कार्य सर्कुलर लिंक्ड लिस्ट में मौजूद नोड्स की संख्या की गणना करना है। सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट का एक प्रकार है जिसमें पहला तत्व अंतिम तत्व की ओर इंगित करता है और अंतिम तत्व पहले तत्व की ओर इंगित करता है। सिंगली लिंक्ड लिस्ट और डबली लिं

  1. C++ में पूर्ण बाइनरी ट्री के नोड्स गिनें C++ में पूर्ण बाइनरी ट्री के नोड्स गिनें

    मान लीजिए हमारे पास एक पूर्ण बाइनरी ट्री है, हमें नोड्स की संख्या गिननी है। तो यदि ट्री इस तरह है −तो आउटपुट 6 होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगेयह रिकर्सिव दृष्टिकोण का उपयोग करेगा। यह मेथड, countNodes() रूट को आर्गुमेंट के रूप में ले रहा है।hr := 0 और hl := 0दो नोड्स l और r

  1. C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें

    मान लीजिए हमारे पास एक धनात्मक पूर्णांक L है, जो परफेक्ट बाइनरी ट्री में स्तरों की संख्या दर्शाता है। इस परफेक्ट बाइनरी ट्री में पत्ती नोड्स को 1 से n तक संख्या दी गई है। जहां n पत्ती नोड्स की संख्या है। पैरेंट नोड बच्चों का योग है। हमारा कार्य इस परफेक्ट बाइनरी ट्री के सभी नोड्स का योग प्रिंट करने