用 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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習