Número mínimo de saltos de Fibonacci para llegar al final

Posted on by Rudeus Greyrat

Dada una array de 0 y 1 , si algún índice en particular i tiene el valor 1 , entonces es un índice seguro y si el valor es 0 , entonces es un índice inseguro . Un hombre que está parado en el índice -1 (fuente) solo puede aterrizar en un índice seguro y tiene que alcanzar el índice N (última posición). En cada salto, el hombre solo puede recorrer una distancia igual a cualquier número de Fibonacci . Debe minimizar el número de pasos, siempre que el hombre solo pueda saltar en dirección hacia adelante.
Nota: Los primeros números de Fibonacci son: 0, 1, 1, 2, 3, 5, 8, 13, 21….
Ejemplos: 
 

Entrada: arr[]= {0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0} 
Salida: 3
La persona saltará de: 
1) índice -1 a índice 4 (una distancia de salto = 5) 
2) índice 4 al índice 6 (una distancia de salto = 2) 
3) índice 6 al destino (una distancia de salto = 5)
Entrada: arr[]= {0, 0} 
Salida: 1
La persona saltará desde: 
1) índice -1 al destino (una distancia de salto = 3) 
 

Acercarse: 
 

  • Primero, crearemos una array fib[] para almacenar números de Fibonacci.
  • Luego, crearemos una array DP y la inicializaremos con INT_MAX y el índice 0 DP[0] = 0 y nos moveremos de la misma manera que el problema de cambio de moneda con un número mínimo de monedas .
  • La definición y recurrencia de DP es la siguiente: 
     
 DP[i] = min( DP[i], 1 + DP[i-fib[j]] )

where i is the current index and j denotes
the jth fibonacci number of which the
jump is possible
    • Aquí DP[i] denota los pasos mínimos requeridos para alcanzar el índice i considerando todos los números de Fibonacci.

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

    C++

    // A Dynamic Programming based
    // C++ program to find minimum
    // number of jumps to reach
    // Destination
    #include <bits/stdc++.h>
    using namespace std;
    #define MAX 1e9
      
    // Function that returns the min
    // number of jump to reach the
    // destination
    int minJumps(int arr[], int N)
    {
        // We consider only those Fibonacci
        // numbers which are less than n,
        // where we can consider fib[30]
        // to be the upper bound as this
        // will cross 10^5
        int fib[30];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < 30; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
      
        // DP[i] will be storing the minimum
        // number of jumps required for
        // the position i. So DP[N+1] will
        // have the result we consider 0
        // as source and N+1 as the destination
        int DP[N + 2];
      
        // Base case (Steps to reach source is)
        DP[0] = 0;
      
        // Initialize all table values as Infinite
        for (int i = 1; i <= N + 1; i++)
            DP[i] = MAX;
      
        // Compute minimum jumps required
        // considering each Fibonacci
        // numbers one by one.
      
        // Go through each positions
        // till destination.
        for (int i = 1; i <= N + 1; i++) {
      
            // Calculate the minimum of that
            // position if all the Fibonacci
            // numbers are considered
            for (int j = 1; j < 30; j++) {
      
                // If the position is safe
                // or the position is the
                // destination then only we
                // calculate the minimum
                // otherwise the cost is
                // MAX as default
                if ((arr[i - 1] == 1
                     || i == N + 1)
                    && i - fib[j] >= 0)
                    DP[i] = min(DP[i],
                                1 + DP[i - fib[j]]);
            }
        }
      
        // -1 denotes if there is
        // no path possible
        if (DP[N + 1] != MAX)
            return DP[N + 1];
        else
            return -1;
    }
      
    // Driver program to test above function
    int main()
    {
        int arr[] = { 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0 };
        int n = sizeof(arr) / sizeof(arr[0]);
      
        cout << minJumps(arr, n);
        return 0;
    }

    Java

    // A Dynamic Programming based 
    // Java program to find minimum 
    // number of jumps to reach 
    // Destination
    import java.util.*; 
    import java.lang.*; 
      
    class GFG 
    {
          
    // Function that returns the min 
    // number of jump to reach the 
    // destination
    public static int minJumps(int arr[], int N) 
    {
        int MAX = 1000000;
          
        // We consider only those Fibonacci 
        // numbers which are less than n, 
        // where we can consider fib[30] 
        // to be the upper bound as this 
        // will cross 10^5 
        int[] fib = new int[30]; 
        fib[0] = 0; 
        fib[1] = 1;
          
        for (int i = 2; i < 30; i++) 
        fib[i] = fib[i - 1] + fib[i - 2]; 
          
        // DP[i] will be storing the minimum 
        // number of jumps required for 
        // the position i. So DP[N+1] will 
        // have the result we consider 0 
        // as source and N+1 as the destination 
        int[] DP = new int[N + 2]; 
          
        // Base case (Steps to reach source is) 
        DP[0] = 0; 
      
        // Initialize all table values as Infinite 
        for (int i = 1; i <= N + 1; i++) 
            DP[i] = MAX; 
      
        // Compute minimum jumps required 
        // considering each Fibonacci 
        // numbers one by one. 
      
        // Go through each positions 
        // till destination. 
        for (int i = 1; i <= N + 1; i++)
        { 
      
            // Calculate the minimum of that 
            // position if all the Fibonacci 
            // numbers are considered 
            for (int j = 1; j < 30; j++) 
            { 
      
                // If the position is safe 
                // or the position is the 
                // destination then only we 
                // calculate the minimum 
                // otherwise the cost is 
                // MAX as default 
                if ((i == N + 1 || 
                     arr[i - 1] == 1) &&
                     i - fib[j] >= 0) 
                    DP[i] = Math.min(DP[i], 1 +
                                     DP[i - fib[j]]); 
            } 
        } 
      
        // -1 denotes if there is 
        // no path possible 
        if (DP[N + 1] != MAX) 
            return DP[N + 1]; 
        else
            return -1; 
    } 
      
    // Driver Code 
    public static void main (String[] args) 
    { 
        int[] arr = new int[]{ 0, 0, 0, 1, 1, 0,
                                  1, 0, 0, 0, 0 }; 
        int n = 11; 
        int ans = minJumps(arr, n); 
        System.out.println(ans); 
    }
    }
      
    // This code is contributed by Mehul

    Python3

    # A Dynamic Programming based Python3 program 
    # to find minimum number of jumps to reach
    # Destination
    MAX = 1e9
      
    # Function that returns the min number 
    # of jump to reach the destination
    def minJumps(arr, N):
          
        # We consider only those Fibonacci
        # numbers which are less than n,
        # where we can consider fib[30]
        # to be the upper bound as this
        # will cross 10^5
        fib = [0 for i in range(30)]
        fib[0] = 0
        fib[1] = 1
        for i in range(2, 30):
            fib[i] = fib[i - 1] + fib[i - 2]
      
        # DP[i] will be storing the minimum
        # number of jumps required for
        # the position i. So DP[N+1] will
        # have the result we consider 0
        # as source and N+1 as the destination
        DP = [0 for i in range(N + 2)]
      
        # Base case (Steps to reach source is)
        DP[0] = 0
      
        # Initialize all table values as Infinite
        for i in range(1, N + 2):
            DP[i] = MAX
      
        # Compute minimum jumps required
        # considering each Fibonacci
        # numbers one by one.
      
        # Go through each positions
        # till destination.
        for i in range(1, N + 2):
      
            # Calculate the minimum of that
            # position if all the Fibonacci
            # numbers are considered
            for j in range(1, 30):
      
                # If the position is safe or the 
                # position is the destination then 
                # only we calculate the minimum
                # otherwise the cost is MAX as default
                if ((arr[i - 1] == 1 or i == N + 1) and 
                                        i - fib[j] >= 0):
                    DP[i] = min(DP[i], 1 + DP[i - fib[j]])
      
        # -1 denotes if there is
        # no path possible
        if (DP[N + 1] != MAX):
            return DP[N + 1]
        else:
            return -1
      
    # Driver Code
    arr = [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0]
    n = len(arr)
      
    print(minJumps(arr, n - 1))
      
    # This code is contributed by Mohit Kumar

    C#

    // A Dynamic Programming based 
    // C# program to find minimum 
    // number of jumps to reach 
    // Destination
    using System;
    using System.Collections.Generic;
      
    class GFG 
    {
          
    // Function that returns the min 
    // number of jump to reach the 
    // destination
    public static int minJumps(int []arr, int N) 
    {
        int MAX = 1000000;
          
        // We consider only those Fibonacci 
        // numbers which are less than n, 
        // where we can consider fib[30] 
        // to be the upper bound as this 
        // will cross 10^5 
        int[] fib = new int[30]; 
        fib[0] = 0; 
        fib[1] = 1;
          
        for (int i = 2; i < 30; i++) 
        fib[i] = fib[i - 1] + fib[i - 2]; 
          
        // DP[i] will be storing the minimum 
        // number of jumps required for 
        // the position i. So DP[N+1] will 
        // have the result we consider 0 
        // as source and N+1 as the destination 
        int[] DP = new int[N + 2]; 
          
        // Base case (Steps to reach source is) 
        DP[0] = 0; 
      
        // Initialize all table values as Infinite 
        for (int i = 1; i <= N + 1; i++) 
            DP[i] = MAX; 
      
        // Compute minimum jumps required 
        // considering each Fibonacci 
        // numbers one by one. 
      
        // Go through each positions 
        // till destination. 
        for (int i = 1; i <= N + 1; i++)
        { 
      
            // Calculate the minimum of that 
            // position if all the Fibonacci 
            // numbers are considered 
            for (int j = 1; j < 30; j++) 
            { 
      
                // If the position is safe 
                // or the position is the 
                // destination then only we 
                // calculate the minimum 
                // otherwise the cost is 
                // MAX as default 
                if ((i == N + 1 || 
                    arr[i - 1] == 1) &&
                    i - fib[j] >= 0) 
                    DP[i] = Math.Min(DP[i], 1 +
                                     DP[i - fib[j]]); 
            } 
        } 
      
        // -1 denotes if there is 
        // no path possible 
        if (DP[N + 1] != MAX) 
            return DP[N + 1]; 
        else
            return -1; 
    } 
      
    // Driver Code 
    public static void Main (String[] args) 
    { 
        int[] arr = new int[]{ 0, 0, 0, 1, 1, 0,
                                  1, 0, 0, 0, 0 }; 
        int n = 11; 
        int ans = minJumps(arr, n); 
        Console.WriteLine(ans); 
    }
    }
      
    // This code is contributed by Princi Singh

    JavaScript

    <script>
      
    // A Dynamic Programming based
    // Javascript program to find minimum
    // number of jumps to reach
    // Destination
      
    const MAX = 1000000000;
      
    // Function that returns the min
    // number of jump to reach the
    // destination
    function minJumps(arr, N)
    {
        // We consider only those Fibonacci
        // numbers which are less than n,
        // where we can consider fib[30]
        // to be the upper bound as this
        // will cross 10^5
        let fib = new Array(30);
        fib[0] = 0;
        fib[1] = 1;
        for (let i = 2; i < 30; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
      
        // DP[i] will be storing the minimum
        // number of jumps required for
        // the position i. So DP[N+1] will
        // have the result we consider 0
        // as source and N+1 as the destination
        let DP = new Array(N + 2);
      
        // Base case (Steps to reach source is)
        DP[0] = 0;
      
        // Initialize all table values as Infinite
        for (let i = 1; i <= N + 1; i++)
            DP[i] = MAX;
      
        // Compute minimum jumps required
        // considering each Fibonacci
        // numbers one by one.
      
        // Go through each positions
        // till destination.
        for (let i = 1; i <= N + 1; i++) {
      
            // Calculate the minimum of that
            // position if all the Fibonacci
            // numbers are considered
            for (let j = 1; j < 30; j++) {
      
                // If the position is safe
                // or the position is the
                // destination then only we
                // calculate the minimum
                // otherwise the cost is
                // MAX as default
                if ((arr[i - 1] == 1
                     || i == N + 1)
                    && i - fib[j] >= 0)
                    DP[i] = Math.min(DP[i],
                                1 + DP[i - fib[j]]);
            }
        }
      
        // -1 denotes if there is
        // no path possible
        if (DP[N + 1] != MAX)
            return DP[N + 1];
        else
            return -1;
    }
      
    // Driver program to test above function
        let arr = [ 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0 ];
        let n = arr.length;
      
        document.write(minJumps(arr, n));
      
    </script>
    Producción: 

    3

     

    Complejidad del tiempo: O(Nlog(N))
     

Publicación traducida automáticamente

Artículo escrito por mehul_02 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *