Gráfico del cubo de Fibonacci

Se le proporciona una entrada como orden del gráfico n (número más alto de aristas conectadas a un Node), debe encontrar el número de vértices en un gráfico de cubo de Fibonacci de orden n.
Ejemplos: 
 

Input : n = 3
Output : 5
Explanation : 
Fib(n + 2) = Fib(5) = 5

Input : n = 2
Output : 3

Un gráfico de cubo de Fibonacci es similar al gráfico de hipercubo , pero con un número de vértices de Fibonacci. En el gráfico del cubo de Fibonacci, solo 1 vértice tiene grado n, el resto tiene un grado menor que n. 
El gráfico del cubo de Fibonacci de orden n tiene F(n + 2) vértices, donde F(n) es un n-ésimo número de Fibonacci , 
serie de Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34…… ………….
 

Para ingresar n como orden del gráfico, encuentre el número de fibonacci correspondiente en la posición n + 2. 
donde F(n) = F(n – 1) + F(n – 2)
Enfoque: encuentre el (n + 2)-ésimo número de fibonacci
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP code to find vertices in a fibonacci
// cube graph of order n
#include<iostream>
using namespace std;
  
// function to find fibonacci number
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
  
// function for finding number of vertices 
// in fibonacci cube graph
int findVertices (int n)
{
    // return fibonacci number for f(n + 2) 
    return fib(n + 2);
}
  
// driver program
int main()
{
    // n is the order of the graph
    int n = 3;
    cout << findVertices(n);
    return 0;
}

// java code to find vertices in a fibonacci
// cube graph of order n
public class GFG {
      
    // function to find fibonacci number
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
      
    // function for finding number of vertices 
    // in fibonacci cube graph
    static int findVertices (int n)
    {
        // return fibonacci number for f(n + 2) 
        return fib(n + 2);
    }
          
    public static void main(String args[]) {
          
        // n is the order of the graph
        int n = 3;
        System.out.println(findVertices(n));
    }
}
  
// This code is contributed by Sam007

# Python3 code to find vertices in 
# a fibonacci cube graph of order n 
  
# Function to find fibonacci number 
def fib(n): 
  
    if n <= 1: 
        return n
          
    return fib(n - 1) + fib(n - 2) 
  
# Function for finding number of 
# vertices in fibonacci cube graph 
def findVertices(n): 
  
    # return fibonacci number 
    # for f(n + 2) 
    return fib(n + 2) 
  
# Driver Code
if __name__ == "__main__": 
  
    # n is the order of the graph 
    n = 3
    print(findVertices(n)) 
  
# This code is contributed 
# by Rituraj Jain

// C# code to find vertices in a fibonacci
// cube graph of order n
using System;
  
class GFG {
      
    // function to find fibonacci number
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
      
    // function for finding number of 
    // vertices in fibonacci cube graph
    static int findVertices (int n)
    {
          
        // return fibonacci number for
        // f(n + 2) 
        return fib(n + 2);
    }
      
    // Driver code
    static void Main()
    {
          
        // n is the order of the graph
        int n = 3;
          
        Console.Write(findVertices(n));
    }
}
  
// This code is contributed by Sam007

<?php
// PHP code to find vertices in a 
// fibonacci cube graph of order n
  
// function to find fibonacci number
function fib($n)
{
    if ($n <= 1)
        return $n;
    return fib($n - 1) + fib($n - 2);
}
  
// function for finding number of  
// vertices in fibonacci cube graph
function findVertices ($n)
{
    // return fibonacci number
    // for f(n + 2) 
    return fib($n + 2);
}
  
// Driver Code
  
// n is the order of the graph
$n = 3;
echo findVertices($n);     
  
// This code is contributed by Sam007
?>

<script>
  
  
// Javascript code to find vertices in a fibonacci
// cube graph of order n
  
// function to find fibonacci number
function fib(n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
  
// function for finding number of vertices 
// in fibonacci cube graph
function findVertices (n)
{
    // return fibonacci number for f(n + 2) 
    return fib(n + 2);
}
  
// driver program
// n is the order of the graph
var n = 3;
document.write( findVertices(n));
  
</script>

5

Tenga en cuenta que el código anterior se puede optimizar para que funcione en O (Log n) usando implementaciones eficientes discutidas en Programa para números de Fibonacci