Xとの合計がC++のフィボナッチ数であるノードをカウントします

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を適用してツリーをトラバースし、ノードの重みと温度がフィボナッチ数になるかどうかを確認します。この目的のために、2つのvectorsNode_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を返します。

• fibを5*num*numで初期化します。

• 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を返す場合、incrementFibonacci。

• forループを使用してベクトルedge_graph[node]のツリーをトラバースします。

• ベクトル内の次のノードに対して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);
   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