नोड्स के वजन वाली एक बाइनरी ट्री दी गई है। लक्ष्य उन नोड्स की संख्या ढूंढना है जिनके वजन ऐसे हैं कि संख्या एक फाइबोनैचि संख्या है। फाइबोनैचि श्रृंखला में संख्याएं हैं: 0, 1, 1, 2, 3, 5, 8, 13... nth संख्या (n-1)th और (n-2)th का योग है। यदि वजन 13 है तो यह एक फाइबोनैचि संख्या है इसलिए नोड गिना जाएगा।
उदाहरण के लिए
इनपुट
temp =1. मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count the nodes whose sum with X is a Fibonacci number are: 3
व्याख्या
हमें ट्री नोड्स और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम जांचते हैं कि क्या temp+weight एक फाइबोनैचि संख्या है या नहीं।
| नोड | वजन | वजन+temp=फाइबोनैचि | हां/नहीं |
|---|---|---|---|
| 2 | 12 | 12+1=13 | हां |
| 1 | 7 | 7+1=8 | हां |
| 4 | 3 | 3+1=4 | नहीं |
| 3 | 4 | 4+1=5 | हां |
| 8 | 19 | 19+1=20 | नहीं |
| 9 | 32 | 32+1=33 | नहीं |
इनपुट
temp = 3. मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count the nodes whose sum with X is a Fibonacci number are: 3
व्याख्या
हमें ट्री नोड्स और प्रत्येक नोड से जुड़े वजन दिए गए हैं। अब हम जांचते हैं कि क्या temp+weight एक फाइबोनैचि संख्या है या नहीं।
| नोड | वजन | वजन+temp=फाइबोनैचि | हां/नहीं |
|---|---|---|---|
| 5 | 23 | 23+3=26 | नहीं |
| 2 | 125 | 125+3=128 | नहीं |
| 6 | 671 | 671+3=674 | नहीं |
| 4 | 212 | 212+3=215 | नहीं |
| 5 | 7171 | 7171+3=7174 | नहीं |
| 3 | 998 | 998+3=1001 | नहीं |
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम ट्री के ग्राफ पर DFS लागू करेंगे इसे ट्रैवर्स करने के लिए और जांचेंगे कि क्या नोड का वजन और temp मिलकर एक फाइबोनैचि संख्या बनाते हैं। इस उद्देश्य के लिए दो वेक्टर Node_Weight(100) और edge_graph[100] लें।
Node_Weight[] को नोड्स के वजन से इनिशियलाइज़ करें।
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
एक ग्लोबल वेरिएबल Fibonacci लें और इसे 0 से इनिशियलाइज़ करें। दूसरा ग्लोबल वेरिएबल temp लें।
फ़ंक्शन check_square(long double val) एक पूर्णांक लेता है और ट्रू लौटाता है यदि val एक परफेक्ट स्क्वायर है।
val_1 = sqrt(val) लें।
अब यदि (val_1 - floor(val_1) == 0) ट्रू लौटाता है तो total एक परफेक्ट स्क्वायर है, ट्रू लौटाएं।
अन्यथा फॉल्स लौटाएं।
फ़ंक्शन check_Fibonacci(int num) एक संख्या लेता है और ट्रू लौटाता है यदि यह एक फाइबोनैचि संख्या है।
fib को 5*num*num से इनिशियलाइज़ करें।
यदि check_square((fib + 4)) || check_square((fib - 4)) ट्रू परिणाम देता है तो ट्रू लौटाएं।
अन्यथा फॉल्स लौटाएं।
फ़ंक्शन Fibonacci_number(int node, int root) उन नोड्स की संख्या लौटाता है जिनका योग X के साथ एक फाइबोनैचि संख्या है।
यदि if(check_Fibonacci(Node_Weight[node] + temp)) ट्रू लौटाता है तो Fibonacci बढ़ाएं।
वेक्टर edge_graph[node] में ट्री को फॉर लूप का उपयोग करके ट्रैवर्स करें।
वेक्टर में अगले नोड के लिए Fibonacci_number(it, node) कॉल करें।
सभी फ़ंक्शन के अंत में हमारे पास Fibonacci उन नोड्स की संख्या के रूप में होगा जिनके वजन का योग temp के साथ एक फाइबोनैचि संख्या है।
उदाहरण
#include <bits/stdc++.h> using namespace std; vectorNode_Weight(100); vector edge_graph[100]; int Fibonacci = 0, temp; bool check_square(long double val){ long double val_1 = sqrt(val); if(val_1 - floor(val_1) == 0){ return true; } return false; } bool check_Fibonacci(int num){ int fib = 5 * num * num; if(check_square((fib + 4)) || check_square((fib - 4))){ return true; } return false; } void Fibonacci_number(int node, int root){ if(check_Fibonacci(Node_Weight[node] + temp)){ Fibonacci++; } for (int it : edge_graph[node]){ if(it == root){ continue; } Fibonacci_number(it, node); } } int main(){ //weight of the nodes Node_Weight[2] = 6; Node_Weight[1] = 4; Node_Weight[4] = 23; Node_Weight[3] = 5; Node_Weight[8] = 161; Node_Weight[9] = 434; //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); temp = 3; Fibonacci_number(2, 2); cout<<"Count the nodes whose sum with X is a Fibonacci number are: "<<Fibonacci; return 0; }
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count the nodes whose sum with X is a Fibonacci number are: 1