C++でXとの合計がフィボナッチ数になるノードを数える方法

各ノードに数値の重みが割り当てられた二分木が与えられます。この記事の目的は、「ノードの重み + X」の計算結果がフィボナッチ数となるノードの個数を求めることです。

フィボナッチ数列とは、0, 1, 1, 2, 3, 5, 8, 13… のように続く数列で、n番目の数は(n−1)番目と(n−2)番目の数の和になります。たとえば重みが13であればフィボナッチ数に該当するため、そのノードはカウント対象となります。

入力例1

temp = 1 の場合。値を入力すると、以下のような木が構成されます。

出力

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

説明

各ノードとその重みが与えられており、「temp + 重み」がフィボナッチ数かどうかを順に判定していきます。

入力例2

temp = 3 の場合。値を入力すると、以下のような木が構成されます。

出力

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

説明

各ノードとその重みが与えられており、「temp + 重み」がフィボナッチ数かどうかを順に判定していきます。

プログラムのアプローチ

このアプローチでは、木に対してDFS(深さ優先探索)を適用して走査を行い、各ノードの重みとtempの和がフィボナッチ数になっているかどうかを確認します。このために、Node_Weight(100) と edge_graph[100] という2つのベクトルを用意します。

• Node_Weight[] を各ノードの重みで初期化します。
• ベクトル edge_graph を使って木(グラフ)を構築します。
• グローバル変数 Fibonacci を宣言し、0で初期化します。グローバル変数 temp も併せて用意します。
• 関数 check_square(long double val) は整数を受け取り、val が完全平方数であれば true を返します。
• まず val_1 = sqrt(val) を計算します。
• if(val_1 − floor(val_1) == 0) が true であれば、val は完全平方数なので true を返します。
• それ以外の場合は false を返します。
• 関数 check_Fibonacci(int num) は数値を受け取り、それがフィボナッチ数であれば true を返します。
• fib = 5 * num * num で初期化します。
• ここで重要なのは、ある整数 n がフィボナッチ数であることと「5n²+4 または 5n²−4 が完全平方数であること」が同値であるという数学的な性質を利用している点です。
• 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(){
   //ノードの重み
   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 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