সংখ্যা হিসাবে এর নোডগুলির ওজন সহ একটি বাইনারি ট্রি দেওয়া হয়েছে৷ লক্ষ্য হল এমন নোডের সংখ্যা খুঁজে বের করা যার ওজন আছে যাতে সংখ্যাটি একটি ফিবোনাচি সংখ্যা। ফিবোনাচি সিরিজের সংখ্যাগুলি হল:0, 1, 1, 2, 3, 5, 8, 13….নম সংখ্যা হল সমষ্টি (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.
| নোড | ওজন | weight+temp=fibonacci | হ্যাঁ/না |
|---|---|---|---|
| 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.
| নোড | ওজন | weight+temp=fibonacci | হ্যাঁ/না |
|---|---|---|---|
| 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 প্রয়োগ করব যাতে এটি অতিক্রম করা যায় এবং নোড এবং টেম্পের ওজন একটি ফিবোনাচি সংখ্যা পর্যন্ত যোগ হয় কিনা তা পরীক্ষা করে দেখব। এই উদ্দেশ্যে দুটি ভেক্টর নোড_ওয়েট(100) এবং এজ_গ্রাফ[100] নিন।
-
নোডের ওজন দিয়ে নোড_ওয়েট[] শুরু করুন।
-
ভেক্টর এজ_গ্রাফ ব্যবহার করে একটি গাছ তৈরি করুন।
-
একটি গ্লোবাল ভেরিয়েবল ফিবোনাচি নিন এবং 0 দিয়ে শুরু করুন। অন্যান্য গ্লোবাল ভ্যারিয়েবল টেম্প নিন।
-
ফাংশন check_square(দীর্ঘ ডবল ভ্যাল) একটি পূর্ণসংখ্যা নেয় এবং যদি val একটি নিখুঁত বর্গ হয় তাহলে সত্য প্রদান করে।
-
val_1 =sqrt(val)
নিন -
এখন যদি (val_1 − floor(val_1) ==0) সত্য ফেরত দেয় তবে মোট একটি নিখুঁত বর্গক্ষেত্র, সত্য ফেরত দেয়।
-
অন্যথায় মিথ্যা ফেরত দিন।
-
ফাংশন check_Fibonacci(int num) একটি সংখ্যা নেয় এবং যদি এটি afibonacci সংখ্যা হয় তাহলে সত্য ফেরত দেয়।
-
5*num*num দিয়ে fib শুরু করুন।
-
যদি check_square((fib + 4)) || check_square((fib − 4)) ফলাফল true তারপর true ফেরত দিন।
-
অন্যথায় মিথ্যা ফেরত দিন।
-
ফাংশন Fibonacci_number(int node, int root) নোডের সংখ্যা প্রদান করে যার যোগফল X এর সাথে একটি ফিবোনাচি সংখ্যা।
-
যদি(check_Fibonacci(Node_Weight[node] + temp)) সত্য হয় তাহলে ফিবোনাচি বৃদ্ধি করুন।
-
লুপের জন্য ব্যবহার করে ভেক্টর এজ_গ্রাফ[নোড] এ ট্র্যাভার্স ট্রি।
-
ভেক্টরের পরবর্তী নোডের জন্য 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
