C++에서 X와의 합이 피보나치 수인 노드를 계산합니다.

노드의 가중치가 숫자인 이진 트리가 제공됩니다. 목표는 숫자가 피보나치 수와 같은 가중치를 갖는 노드의 수를 찾는 것입니다. 피보나치 수열의 숫자는 다음과 같습니다. 0, 1, 1, 2, 3, 5, 8, 13...n번째 숫자는 다음의 합입니다. (n-1)번째 및 (n-2)번째. 가중치가 13이면 피보나치 수이므로 노드가 계산됩니다.

예

입력

온도 =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를 적용하여 트리를 탐색하고 노드와 온도의 가중치가 피보나치 수에 합산되는지 확인합니다. 이를 위해 두 개의 vectorNode_Weight(100) 및 edge_graph[100]를 사용합니다.

• 노드의 가중치로 Node_Weight[]를 초기화합니다.

• 벡터 edge_graph를 사용하여 나무를 만듭니다.

• 전역 변수 피보나치를 가져와 0으로 초기화합니다. 다른 전역 변수 temp를 사용합니다.

• check_square(long double val) 함수는 정수를 취하고 val이 완전제곱이면 true를 반환합니다.

• val_1 =sqrt(val)

• 이제 if(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[노드]에서 트리를 탐색합니다.

• 벡터의 다음 노드에 대해 Fibonacci_number(it, node)를 호출합니다.

• 모든 함수의 끝에서 우리는 피보나치 수로 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