Encuentre los números presentes en el nivel K de un árbol binario de Fibonacci

Dado un número K , la tarea es imprimir los números de Fibonacci presentes en el nivel K de un árbol binario de Fibonacci .
Ejemplos: 
 

Input: K = 3
Output: 2, 3, 5, 8
Explanation:
Fibonacci Binary Tree for 3 levels:
        0
       / \
      1   1
     /\  / \
    2  3 5  8
Numbers present at level 3: 2, 3, 5, 8

Input: K = 2
Output: 1, 1
Explanation:
Fibonacci Binary Tree for 2 levels:
        0
       / \
      1   1
Numbers present at level 2: 1, 1

Enfoque ingenuo: el enfoque ingenuo es construir un árbol binario de Fibonacci ( árbol binario de números de Fibonacci) y luego obtener elementos en un nivel K particular. 
Sin embargo, este enfoque es obsoleto para números grandes, ya que lleva demasiado tiempo.
Enfoque eficiente: dado que los elementos que estarían presentes en algún nivel arbitrario K del árbol se pueden encontrar encontrando los elementos en el rango [2 ^{K – 1} , 2 ^K – 1] . Por lo tanto: 
 

1. Encuentre los números de Fibonacci hasta 10 ⁶ utilizando Programación Dinámica y guárdelos en una array.
2. Calcule el índice izquierdo y el índice derecho del nivel como:

left_index = 2K - 1 
right_index = 2K - 1

1. Imprima los números de Fibonacci desde el índice izquierdo al índice derecho de la array de Fibonacci.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to print the Fibonacci numbers
// present at K-th level of a Binary Tree
 
#include <bits/stdc++.h>
using namespace std;
 
// Initializing the max value
#define MAX_SIZE 100005
 
// Array to store all the
// fibonacci numbers
int fib[MAX_SIZE + 1];
 
// Function to generate fibonacci numbers
// using Dynamic Programming
void fibonacci()
{
    int i;
 
    // 0th and 1st number of the series
    // are 0 and 1
    fib[0] = 0;
    fib[1] = 1;
 
    for (i = 2; i <= MAX_SIZE; i++) {
 
        // Add the previous two numbers in the
        // series and store it
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
 
// Function to print the Fibonacci numbers
// present at Kth level of a Binary Tree
void printLevel(int level)
{
    // Finding the left and right index
    int left_index = pow(2, level - 1);
    int right_index = pow(2, level) - 1;
 
    // Iterating and printing the numbers
    for (int i = left_index;
         i <= right_index; i++) {
 
        cout << fib[i - 1] << " ";
    }
    cout << endl;
}
 
// Driver code
int main()
{
    // Precomputing Fibonacci numbers
    fibonacci();
 
    int K = 4;
    printLevel(K);
 
    return 0;
}

// Java program to print the Fibonacci numbers
// present at K-th level of a Binary Tree
import java.util.*;
 
class GFG{
  
// Initializing the max value
static final int MAX_SIZE = 100005;
  
// Array to store all the
// fibonacci numbers
static int []fib = new int[MAX_SIZE + 1];
  
// Function to generate fibonacci numbers
// using Dynamic Programming
static void fibonacci()
{
    int i;
  
    // 0th and 1st number of the series
    // are 0 and 1
    fib[0] = 0;
    fib[1] = 1;
  
    for (i = 2; i <= MAX_SIZE; i++) {
  
        // Add the previous two numbers in the
        // series and store it
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
  
// Function to print the Fibonacci numbers
// present at Kth level of a Binary Tree
static void printLevel(int level)
{
    // Finding the left and right index
    int left_index = (int) Math.pow(2, level - 1);
    int right_index = (int) (Math.pow(2, level) - 1);
  
    // Iterating and printing the numbers
    for (int i = left_index;
         i <= right_index; i++) {
  
        System.out.print(fib[i - 1]+ " ");
    }
    System.out.println();
}
  
// Driver code
public static void main(String[] args)
{
    // Precomputing Fibonacci numbers
    fibonacci();
  
    int K = 4;
    printLevel(K);
}
}
 
// This code is contributed by Rajput-Ji

# Python program to print the Fibonacci numbers
# present at K-th level of a Binary Tree
 
# Initializing the max value
MAX_SIZE = 100005
 
# Array to store all the
# fibonacci numbers
fib =[0]*(MAX_SIZE + 1)
 
# Function to generate fibonacci numbers
# using Dynamic Programming
def fibonacci():
     
    # 0th and 1st number of the series
    # are 0 and 1
    fib[0] = 0
    fib[1] = 1
     
    for i in range(2, MAX_SIZE + 1):
         
        # Add the previous two numbers in the
        # series and store it
        fib[i] = fib[i - 1] + fib[i - 2]
         
# Function to print the Fibonacci numbers
# present at Kth level of a Binary Tree
def printLevel(level):
     
    # Finding the left and right index
    left_index = pow(2, level - 1)
    right_index = pow(2, level) - 1
     
    # Iterating and printing the numbers
    for i in range(left_index, right_index+1):
        print(fib[i - 1],end=" ")
         
    print()
 
# Driver code
 
# Precomputing Fibonacci numbers
fibonacci()
 
K = 4
printLevel(K)
 
# This code is contributed by shivanisinghss2110

// C# program to print the Fibonacci numbers
// present at K-th level of a Binary Tree
using System;
 
class GFG{
     
    // Initializing the max value
    static int MAX_SIZE = 100005;
     
    // Array to store all the
    // fibonacci numbers
    static int []fib = new int[MAX_SIZE + 1];
     
    // Function to generate fibonacci numbers
    // using Dynamic Programming
    static void fibonacci()
    {
        int i;
     
        // 0th and 1st number of the series
        // are 0 and 1
        fib[0] = 0;
        fib[1] = 1;
     
        for (i = 2; i <= MAX_SIZE; i++) {
     
            // Add the previous two numbers in the
            // series and store it
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
     
    // Function to print the Fibonacci numbers
    // present at Kth level of a Binary Tree
    static void printLevel(int level)
    {
        // Finding the left and right index
        int left_index = (int) Math.Pow(2, level - 1);
        int right_index = (int) (Math.Pow(2, level) - 1);
     
        // Iterating and printing the numbers
        for (int i = left_index;
            i <= right_index; i++) {
     
            Console.Write(fib[i - 1]+ " ");
        }
            Console.WriteLine();
    }
     
    // Driver code
    public static void Main(string[] args)
    {
        // Precomputing Fibonacci numbers
        fibonacci();
     
        int K = 4;
        printLevel(K);
    }
}
 
// This code is contributed by Yash_R

<script>
 
// Javascript program to print the Fibonacci numbers
// present at K-th level of a Binary Tree
 
    // Initializing the max value
     var MAX_SIZE = 100005;
 
    // Array to store all the
    // fibonacci numbers
    var fib = Array(MAX_SIZE + 1).fill(0);
 
    // Function to generate fibonacci numbers
    // using Dynamic Programming
    function fibonacci()
    {
        var i;
 
        // 0th and 1st number of the series
        // are 0 and 1
        fib[0] = 0;
        fib[1] = 1;
 
        for (i = 2; i <= MAX_SIZE; i++)
        {
 
            // Add the previous two numbers in the
            // series and store it
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
 
    // Function to print the Fibonacci numbers
    // present at Kth level of a Binary Tree
    function printLevel(level)
    {
        // Finding the left and right index
        var left_index =
        parseInt( Math.pow(2, level - 1));
        var right_index =
        parseInt( (Math.pow(2, level) - 1));
 
        // Iterating and printing the numbers
        for (i = left_index; i <= right_index; i++)
        {
 
            document.write(fib[i - 1] + " ");
        }
        document.write();
    }
 
    // Driver code
     
        // Precomputing Fibonacci numbers
        fibonacci();
 
        var K = 4;
        printLevel(K);
 
// This code contributed by umadevi9616
 
</script>

13 21 34 55 89 144 233 377