นับโหนดที่น้ำหนักบวก X ได้เลขฟีโบนัชชี ใน C++

โจทย์: ให้ Binary Tree ที่โหนดมีน้ำหนัก (weight) และค่า X ต้องการนับโหนดที่ weight + X เป็นเลขฟีโบนัชชี

การตรวจสอบเลขฟีโบนัชชี

เลข n เป็นฟีโบนัชชี ก็ต่อเมื่อ 5n² + 4 หรือ 5n² - 4 เป็นจำนวนกำลังสองสมบูรณ์

bool check_square(long double val) {
    long double val_1 = sqrt(val);
    return (val_1 - floor(val_1) == 0);
}

bool check_Fibonacci(int num) {
    int fib = 5 * num * num;
    return check_square(fib + 4) || check_square(fib - 4);
}

DFS บนต้นไม้

vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int Fibonacci = 0, temp;

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);
    }
}

ตัวอย่างเต็ม

#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);
    return (val_1 - floor(val_1) == 0);
}

bool check_Fibonacci(int num) {
    int fib = 5 * num * num;
    return check_square(fib + 4) || check_square(fib - 4);
}

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: " << Fibonacci;
    return 0;
}

ผลลัพธ์

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