用 C++ 统计节点权重与 X 相加为斐波那契数的节点数量

给定一棵二叉树，其节点权重为数字。目标是找到权重为斐波那契数的节点数量。斐波那契数列中的数字为：0、1、1、2、3、5、8、13……第 n 个数是第 (n−1) 个数和第 (n−2) 个数的和。如果权重为 13，则它是一个斐波那契数，因此该节点将被计数。

例如

输入

temp = 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.

输入

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.

下面程序中使用的方案如下：

在此方案中，我们将对树的图形应用深度优先搜索 (DFS) 来遍历它并检查节点的权重和 temp 是否加起来为斐波那契数。为此，请使用两个向量 Node_Weight(100) 和 edge_graph[100]。

• 用节点的权重初始化 Node_Weight[]。

• 使用向量 edge_graph 创建树。

• 取一个全局变量 Fibonacci 并将其初始化为 0。取另一个全局变量 temp。

• 函数 check_square(long double val) 获取一个整数，如果 val 是一个完全平方数，则返回 true。

• 取 val_1 = sqrt(val)

• 现在，如果 (val_1 − floor(val_1) == 0) 返回 true，则 total 是一个完全平方数，返回 true。

• 否则返回 false。

• 函数 check_Fibonacci(int num) 获取一个数字，如果它是斐波那契数，则返回 true。

• 用 5*num*num 初始化 fib。

• 如果 check_square((fib + 4)) || check_square((fib − 4)) 结果为 true，则返回 true。

• 否则返回 false。

• 函数 Fibonacci_number(int node, int root) 返回权重与 X 相加为斐波那契数的节点数量。

• 如果 if(check_Fibonacci(Node_Weight[node] + temp)) 返回 true，则递增 Fibonacci。

• 使用 for 循环遍历向量 edge_graph[node] 中的树。

• 对向量中的下一个节点调用 Fibonacci_number(it, node)。

• 在所有函数结束时，我们将拥有一个 Fibonacci 作为权重与 temp 相加为斐波那契数的节点数。

示例

 在线演示

#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

Sunidhi Bansal

更新于： 2021 年 1 月 7 日

104 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习