ফিবোনাচ্চি সংখ্যা যেন করা নোডের ওজন এবং X-এর যোগফল C++-এ

একটি বাইনারি ট্রি দেওয়া আছে যার নোডগুলোর ওজন সংখ্যা হিসেবে আছে। লক্ষ্য হলো সেই নোডগুলোর সংখ্যা বের করা যাদের ওজন আর X-এর যোগফল একটি ফিবোনাচ্চি সংখ্যা হয়। ফিবোনাচ্চি সিরিজ: 0, 1, 1, 2, 3, 5, 8, 13... nth সংখ্যা = (n-1)th + (n-2)th। যদি ওজন ১৩ হয় তবে সেটি ফিবোনাচ্চি সংখ্যা, সুতরাং নোডটি গণনা হবে।

ইনপুট

temp = 1। ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes whose sum with X is a Fibonacci number are: 3

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন চেক করা হচ্ছে temp+ওজন ফিবোনাচ্চি সংখ্যা কিনা।

ইনপুট

temp = 3। ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes whose sum with X is a Fibonacci number are: 3

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন চেক করা হচ্ছে temp+ওজন ফিবোনাচ্চি সংখ্যা কিনা।

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

এই পদ্ধতিতে আমরা ট্রির গ্রাফে DFS অ্যাপ্লাই করি ট্রভারস করতে এবং চেক করি নোডের ওজন আর temp যোগ করলে ফিবোনাচ্চি সংখ্যা হয় কিনা। দুটি ভেক্টর Node_Weight(100) এবং edge_graph[100] নেওয়া হয়।

• Node_Weight[] নোডের ওজন দিয়ে ইনিশিয়ালাইজ করা হয়।
• edge_graph ভেক্টর দিয়ে ট্রি তৈরি করা হয়।
• গ্লোবাল ভেরিয়েবল Fibonacci ০ দিয়ে ইনিশিয়ালাইজ এবং অন্য গ্লোবাল ভেরিয়েবল temp।
• check_square(long double val) ফাংশন ইন্টিজার নিয়ে পারফেক্ট স্কয়ার কিনা চেক করে।
• val_1 = sqrt(val) এবং val_1 - floor(val_1) == 0 হলে true রিটার্ন।
• check_Fibonacci(int num) ফাংশন ফিবোনাচ্চি সংখ্যা কিনা চেক করে।
• fib = 5*num*num এবং check_square(fib+4) || check_square(fib-4) হলে true।
• Fibonacci_number(int node, int root) ফাংশন নোড কাউন্ট রিটার্ন করে যাদের ওজন+temp ফিবোনাচ্চি।
• check_Fibonacci(Node_Weight[node] + temp) true হলে Fibonacci++।
• edge_graph[node] ট্রভারস করে রিকারসিভ কল Fibonacci_number(it, node)।
• শেষে Fibonacci ভেরিয়েবলে প্রয়োজনীয় কাউন্ট পাওয়া যায়।

উদাহরণ

#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() {
    // নোডের ওজন
    Node_Weight[2] = 6;
    Node_Weight[1] = 4;
    Node_Weight[4] = 23;
    Node_Weight[3] = 5;
    Node_Weight[8] = 161;
    Node_Weight[9] = 434;
    // গ্রাফ এজ তৈরি
    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