एक बाइनरी ट्री दिया गया है जिसके नोड्स के भार संख्याओं के रूप में हैं। लक्ष्य उन नोड्स की संख्या का पता लगाना है जिनका वजन इस तरह है कि संख्या एक फाइबोनैचि संख्या है। फाइबोनैचि श्रृंखला में संख्याएं हैं:0, 1, 1, 2, 3, 5, 8, 13…। n वीं संख्या का योग है (n−1)वें और (n−2)वें। अगर वजन 13 है तो यह एक फाइबोनैचि संख्या है इसलिए नोड की गणना की जाएगी।
उदाहरण के लिए
इनपुट
अस्थायी =1। मान डालने के बाद जो ट्री बनाया जाएगा वह नीचे दिया गया है -
आउटपुट
Count the nodes whose sum with X is a Fibonacci number are: 3
स्पष्टीकरण
we are given with the tree nodes and the weights associated with each node. Now we check whether the temp+weight is a Fibonacci number or not.
| नोड | <थ>वजनवजन+अस्थायी=फिबोनैकी | हां/नहीं | |
|---|---|---|---|
| 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
स्पष्टीकरण
we are given with the tree nodes and the weights associated with each node. Now we check whether the temp+weight is a Fibonacci number or not.
| नोड | <थ>वजनवजन+अस्थायी=फिबोनैकी | हां/नहीं | |
|---|---|---|---|
| 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 | नहीं |
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम पेड़ के ग्राफ पर इसे पार करने के लिए डीएफएस लागू करेंगे और जांचेंगे कि नोड और अस्थायी के वजन एक फाइबोनैकी संख्या तक जुड़ते हैं या नहीं। इस उद्देश्य के लिए दो वैक्टर Node_Weight(100) और edge_graph[100] लें।
-
नोड्स के भार के साथ Node_Weight[] प्रारंभ करें।
-
वेक्टर edge_graph का उपयोग करके एक ट्री बनाएं।
-
एक वैश्विक चर Fibonacci लें और इसे 0 से प्रारंभ करें। अन्य वैश्विक चर अस्थायी लें।
-
फंक्शन check_square(long double val) एक पूर्णांक लेता है और अगर वैल एक पूर्ण वर्ग है तो सही लौटाता है।
-
val_1 =sqrt(val) लें
-
अब अगर(val_1 − floor(val_1) ==0) सही है तो कुल एक पूर्ण वर्ग है, सही लौटें।
-
अन्यथा झूठी वापसी करें।
-
फ़ंक्शन check_Fibonacci(int num) एक नंबर लेता है और अगर यह एफ़िबोनैकी नंबर है तो सही रिटर्न देता है।
-
5*num*num के साथ फ़ाइब को इनिशियलाइज़ करें।
-
अगर check_square((फ़ाइब + 4)) || check_square((फ़ाइब - 4)) परिणाम सही है और फिर सही है।
-
अन्यथा झूठी वापसी करें।
-
फंक्शन Fibonacci_number(int node, int root) उन नोड्स की गिनती लौटाता है जिनका योग X के साथ एक फिबोनाची संख्या है।
-
अगर if(check_Fibonacci(Node_Weight[node] + temp)) सही है तो इंक्रीमेंटफिबोनैचि।
-
लूप के लिए उपयोग कर वेक्टर edge_graph[नोड] में ट्रैवर्स ट्री।
-
वेक्टर में अगले नोड के लिए Fibonacci_number(it, node) पर कॉल करें।
-
सभी कार्यों के अंत में हमारे पास एक फाइबोनैचि संख्या के रूप में अस्थायी के साथ योग वाले भार वाले नोड्स की संख्या के रूप में एक फाइबोनैचि होगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> 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