Đếm nút có trọng số cộng X là số Fibonacci trong C++

Cho cây với trọng số nút. Đếm số nút mà trọng_số + X là số Fibonacci.

Ý tưởng

• Dùng DFS duyệt cây (biểu diễn bằng danh sách kề edge_graph và mảng trọng số Node_Weight).
• Kiểm tra số Fibonacci bằng tính chất: 5*n^2 + 4 hoặc 5*n^2 - 4 là số chính phương.
• Hàm check_square kiểm tra số chính phương.

Ví dụ hoàn chỉnh

#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 << "Số nút có trọng số + X là Fibonacci: " << Fibonacci;
    return 0;
}

Kết quả

Số nút có trọng số + X là Fibonacci: 1