Dado un árbol con los pesos de todos los Nodes, la tarea es contar el número de Nodes cuyo peso es un número de Fibonacci.
Ejemplos:
Aporte:
Salida: 2
Explicación:
Los Nodes que tienen pesos 5 y 8 son Nodes de Fibonacci.
Aporte:
Salida: 3
Explicación:
Los Nodes que tienen pesos 1, 3 y 8 son Nodes de Fibonacci.
Enfoque: La idea es realizar un dfs en el árbol y para cada Node, verificar si el peso es un número de Fibonacci o no.
- Genere un hash que contenga todos los números de Fibonacci utilizando la programación dinámica .
- Usando el recorrido de búsqueda primero en profundidad, recorra cada Node del árbol y verifique si el Node es un número de Fibonacci o no al verificar si ese elemento está presente en el hash precalculado o no.
- Finalmente, imprima el número total de Nodes de Fibonacci.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of nodes // in the tree whose weight is a // Fibonacci number #include <bits/stdc++.h> using namespace std; const int sz = 1e5; int ans = 0; vector<int> graph[100]; vector<int> weight(100); // To store all fibonacci numbers set<int> fib; // Function to generate fibonacci numbers using // Dynamic Programming and create hash table // to check Fibonacci numbers void fibonacci() { // Inserting the first two Fibonacci numbers // in the hash int prev = 0, curr = 1, len = 2; fib.insert(prev); fib.insert(curr); // Computing the Fibonacci numbers until // the maximum number and storing them // in the hash while (len <= sz) { int temp = curr + prev; fib.insert(temp); prev = curr; curr = temp; len++; } } // Function to perform dfs void dfs(int node, int parent) { // Check if the weight of the node // is a Fibonacci number or not if (fib.find(weight[node]) != fib.end()) ans += 1; // Performing DFS to iterate the // remaining nodes for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); } } // Driver code int main() { // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].push_back(2); graph[2].push_back(3); graph[2].push_back(4); graph[1].push_back(5); // Generate fibonacci numbers fibonacci(); // Call the dfs function to // traverse through the tree dfs(1, 1); cout << ans << endl; return 0; }
Java
// Java program to count the number of nodes // in the tree whose weight is a // Fibonacci number import java.util.*; class GFG{ static int sz = (int) 1e5; static int ans = 0; static Vector<Integer> []graph = new Vector[100]; static int []weight = new int[100]; // To store all fibonacci numbers static HashSet<Integer> fib = new HashSet<Integer>(); // Function to generate fibonacci numbers using // Dynamic Programming and create hash table // to check Fibonacci numbers static void fibonacci() { // Inserting the first two Fibonacci numbers // in the hash int prev = 0, curr = 1, len = 2; fib.add(prev); fib.add(curr); // Computing the Fibonacci numbers until // the maximum number and storing them // in the hash while (len <= sz) { int temp = curr + prev; fib.add(temp); prev = curr; curr = temp; len++; } } // Function to perform dfs static void dfs(int node, int parent) { // Check if the weight of the node // is a Fibonacci number or not if (fib.contains(weight[node])) ans += 1; // Performing DFS to iterate the // remaining nodes for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); } } // Driver code public static void main(String[] args) { for(int i = 0; i < 100; i++) { graph[i] = new Vector<Integer>(); } // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].add(2); graph[2].add(3); graph[2].add(4); graph[1].add(5); // Generate fibonacci numbers fibonacci(); // Call the dfs function to // traverse through the tree dfs(1, 1); System.out.print(ans +"\n"); } } // This code is contributed by Rajput-Ji
Python3
# Python 3 program to count the number of nodes # in the tree whose weight is a # Fibonacci number sz = 1e5 ans = 0 graph = [[] for i in range(100)] weight = [0 for i in range(100)] # To store all fibonacci numbers fib = set() # Function to generate fibonacci numbers using # Dynamic Programming and create hash table # to check Fibonacci numbers def fibonacci(): # Inserting the first two Fibonacci numbers # in the hash prev = 0 curr = 1 len1 = 2 fib.add(prev) fib.add(curr) # Computing the Fibonacci numbers until # the maximum number and storing them # in the hash while (len1 <= sz): temp = curr + prev fib.add(temp) prev = curr; curr = temp; len1 += 1 # Function to perform dfs def dfs(node, parent): global ans # Check if the weight of the node # is a Fibonacci number or not if (weight[node] in fib): ans += 1 # Performing DFS to iterate the # remaining nodes for to in graph[node]: if (to == parent): continue dfs(to, node) # Driver code if __name__ == '__main__': # Weights of the node weight[1] = 5 weight[2] = 10 weight[3] = 11 weight[4] = 8 weight[5] = 6 # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) # Generate fibonacci numbers fibonacci() # Call the dfs function to # traverse through the tree dfs(1, 1) print(ans) # This code is contributed by Surendra_Gangwar
C#
// C# program to count the number of nodes // in the tree whose weight is a // Fibonacci number using System; using System.Collections.Generic; public class GFG{ static int sz = (int) 1e5; static int ans = 0; static List<int> []graph = new List<int>[100]; static int []weight = new int[100]; // To store all fibonacci numbers static HashSet<int> fib = new HashSet<int>(); // Function to generate fibonacci numbers using // Dynamic Programming and create hash table // to check Fibonacci numbers static void fibonacci() { // Inserting the first two Fibonacci numbers // in the hash int prev = 0, curr = 1, len = 2; fib.Add(prev); fib.Add(curr); // Computing the Fibonacci numbers until // the maximum number and storing them // in the hash while (len <= sz) { int temp = curr + prev; fib.Add(temp); prev = curr; curr = temp; len++; } } // Function to perform dfs static void dfs(int node, int parent) { // Check if the weight of the node // is a Fibonacci number or not if (fib.Contains(weight[node])) ans += 1; // Performing DFS to iterate the // remaining nodes foreach (int to in graph[node]) { if (to == parent) continue; dfs(to, node); } } // Driver code public static void Main(String[] args) { for(int i = 0; i < 100; i++) { graph[i] = new List<int>(); } // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].Add(2); graph[2].Add(3); graph[2].Add(4); graph[1].Add(5); // Generate fibonacci numbers fibonacci(); // Call the dfs function to // traverse through the tree dfs(1, 1); Console.Write(ans +"\n"); } } // This code contributed by Rajput-Ji
Javascript
<script> // JavaScript program to count the number of nodes // in the tree whose weight is a // Fibonacci number var sz = 1000000; var ans = 0; var graph = Array.from(Array(100), ()=>Array()); var weight = Array(100); // To store all fibonacci numbers var fib = new Set(); // Function to generate fibonacci numbers using // Dynamic Programming and create hash table // to check Fibonacci numbers function fibonacci() { // Inserting the first two Fibonacci numbers // in the hash var prev = 0, curr = 1, len = 2; fib.add(prev); fib.add(curr); // Computing the Fibonacci numbers until // the maximum number and storing them // in the hash while (len <= sz) { var temp = curr + prev; fib.add(temp); prev = curr; curr = temp; len++; } } // Function to perform dfs function dfs(node, parent) { // Check if the weight of the node // is a Fibonacci number or not if (fib.has(weight[node])) ans += 1; // Performing DFS to iterate the // remaining nodes for(var to of graph[node]) { if (to == parent) continue; dfs(to, node); } } // Driver code // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].push(2); graph[2].push(3); graph[2].push(4); graph[1].push(5); // Generate fibonacci numbers fibonacci(); // Call the dfs function to // traverse through the tree dfs(1, 1); document.write(ans +"<br>"); </script>
Producción:
2
Análisis de Complejidad:
- Complejidad temporal: O(N).
En dfs, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida a dfs es O(N) si hay un total de N Nodes en el árbol. Además, para procesar cada Node se utiliza la función fibonacci(), que también tiene una complejidad de O(N), pero dado que esta función se ejecuta solo una vez, no afecta la complejidad temporal general. Por lo tanto, la complejidad del tiempo es O(N). - Espacio Auxiliar : O(N).
Se utiliza espacio extra para el hashset de Fibonacci, por lo que la complejidad del espacio es O(N).
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA