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

C++ में दिए गए ट्री में उन नोड्स को गिनना जिनका वजन दो की घात है


नोड्स के वजन वाली एक बाइनरी ट्री दी गई है। लक्ष्य उन नोड्स की संख्या ढूंढना है जिनके वजन ऐसे हैं कि संख्या दो की घात है। यदि वजन 32 है तो यह 2⁵ है इसलिए यह नोड गिना जाएगा।

उदाहरण के लिए

इनपुट

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

C++ में दिए गए ट्री में उन नोड्स को गिनना जिनका वजन दो की घात है

आउटपुट

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

व्याख्या

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


नोडवजनवजन^22 की घात
282*2*2नहीं
110010*2हां
4211अभाज्य संख्यानहीं
3164^2हां
81717संभव नहींनहीं
9322*2*2*2*2हां

इनपुट

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

C++ में दिए गए ट्री में उन नोड्स को गिनना जिनका वजन दो की घात है

आउटपुट

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

व्याख्या

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


नोडवजनवजन ^ 22 की घात
2164^2हां
1141संभव नहींनहीं
441अभाज्य संख्यानहीं
3648^2हां
8819^2हां

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

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

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

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

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

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

  • set = Node_Weight[node] लें।

  • यदि set && (!(set & (set - 1))) ट्रू लौटाता है तो यह दो की घात है (बिटवाइज़ AND और फिर नेगेशन)।

  • powers बढ़ाएं क्योंकि set का मान 2 की घात है।

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

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

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

उदाहरण

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

  1. C++ में दिए गए बाइनरी ट्री के सभी स्तरों पर गैर-पत्ती नोड्स का अधिकतम योग (Maximum sum of non-leaf nodes among all levels) C++ में दिए गए बाइनरी ट्री के सभी स्तरों पर गैर-पत्ती नोड्स का अधिकतम योग (Maximum sum of non-leaf nodes among all levels)

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में दिए गए बाइनरी ट्री के सभी स्तरों पर गैर-पत्ती नोड्स (non-leaf nodes) का अधिकतम योग ढूंढे। समस्या विवरण - हम ट्री के हर स्तर पर सभी गैर-पत्ती नोड्स का योग निकालेंगे और फिर अधिकतम योग प्रिंट करेंगे। आइए एक उद

  1. C++ में बाइनरी ट्री में दो दिए गए लेवल के बीच सभी नोड्स प्रिंट करना C++ में बाइनरी ट्री में दो दिए गए लेवल के बीच सभी नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी ट्री और ट्री में दो लेवल दिए गए हैं (ऊपरी और निचला) और हमें ट्री के ऊपरी और निचले लेवल के बीच के सभी नोड्स प्रिंट करने हैं। बाइनरी ट्री बाइनरी ट्री एक विशेष ट्री है जिसके प्रत्येक नोड में अधिकतम दो नोड्स होते हैं (एक/दो/कोई नहीं)। उदाहरण ऊपरी - 1 निचला - 3 आउटपुट -

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

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