Рубрики

Минимальное количество прыжков для достижения конца

Дан массив целых чисел, где каждый элемент представляет максимальное количество шагов, которые можно сделать вперед из этого элемента. Напишите функцию, которая будет возвращать минимальное количество прыжков для достижения конца массива (начиная с первого элемента). Если элемент равен 0, то не может пройти через этот элемент.

Пример:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)

Первый элемент равен 1, поэтому можно перейти только к 3. Второй элемент равен 3, поэтому можно сделать не более 3 шагов, например, до 5, 8 или 9.

Метод 1 (Наивный рекурсивный подход)
Наивный подход состоит в том, чтобы начать с первого элемента и рекурсивно вызвать все элементы, достижимые из первого элемента. Минимальное количество прыжков для достижения конца с первого может быть рассчитано с использованием минимального количества прыжков, необходимых для достижения конца от элементов, достижимых с первого.

minJumps (начало, конец) = Min (minJumps (k, конец)) для всех k, достижимых с начала

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата минимального числа
// прыжков для достижения arr [h] из arr [l]

int minJumps(int arr[], int n)

{

  

    // Базовый случай: когда источник и

    // пункт назначения одинаков

    if (n == 1)

        return 0;

  

    // Обход всех точек

    // достижимы от arr [l]

    // Рекурсив, получаем минимальное количество

    // прыжков, необходимых для достижения arr [h] из

    // эти достижимые точки

    int res = INT_MAX;

    for (int i = n - 2; i >= 0; i--) {

        if (i + arr[i] >= n - 1) {

            int sub_res = minJumps(arr, i + 1);

            if (sub_res != INT_MAX)

                res = min(res, sub_res + 1);

        }

    }

  

    return res;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 3, 6, 3, 2,

                  3, 6, 8, 9, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Minimum number of jumps to";

    cout << " reach the end is " << minJumps(arr, n);

    return 0;

}

  
// Этот код добавлен
// от Shivi_Aggarwal

С

#include <limits.h>
#include <stdio.h>

  
// Возвращает минимальное количество прыжков для достижения arr [h] из arr [l]

int minJumps(int arr[], int l, int h)

{

    // Базовый случай: когда источник и пункт назначения совпадают

    if (h == l)

        return 0;

  

    // Когда ничего не доступно из заданного источника

    if (arr[l] == 0)

        return INT_MAX;

  

    // Пройти через все точки, достижимые из arr [l]. Рекурсивный

    // получаем минимальное количество прыжков, необходимое для достижения arr [h] из этих

    // достижимые точки.

    int min = INT_MAX;

    for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {

        int jumps = minJumps(arr, i, h);

        if (jumps != INT_MAX && jumps + 1 < min)

            min = jumps + 1;

    }

  

    return min;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Minimum number of jumps to reach end is %d ", minJumps(arr, 0, n - 1));

    return 0;

}

Джава

// Явапрограмма для поиска минимума
// количество прыжков до конца

import java.util.*;

import java.io.*;

  

class GFG {

    // Возвращает минимальное количество

    // прыгает, чтобы достичь arr [h] от arr [l]

    static int minJumps(int arr[], int l, int h)

    {

        // Базовый случай: когда источник

        // и пункт назначения одинаков

        if (h == l)

            return 0;

  

        // Когда ничего не достижимо

        // из данного источника

        if (arr[l] == 0)

            return Integer.MAX_VALUE;

  

        // Обход всех точек

        // достижимо из arr [l]. Рекурсивный

        // получаем минимальное количество прыжков

        // необходимо достичь arr [h] из этих

        // достижимые точки.

        int min = Integer.MAX_VALUE;

        for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {

            int jumps = minJumps(arr, i, h);

            if (jumps != Integer.MAX_VALUE && jumps + 1 < min)

                min = jumps + 1;

        }

        return min;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int arr[] = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };

        int n = arr.length;

        System.out.print("Minimum number of jumps to reach end is "

                         + minJumps(arr, 0, n - 1));

    }

}

  
// Этот код предоставлен Sahil_Bansall

python3

# Python3 программа для поиска минимума
# количество прыжков до конца

  
# Возвращает минимальное количество прыжков
# достичь arr [h] из arr [l]

def minJumps(arr, l, h):

  

    # Базовый случай: когда источник и

    # пункт назначения одинаков

    if (h == l):

        return 0

  

    # когда ничего не достижимо

    # из данного источника

    if (arr[l] == 0):

        return float('inf')

  

    # Пройдите через все точки

    # достижимо от обр [l]. Рекурсивный

    # получить минимальное количество прыжков

    # необходимо достичь arr [h] из

    # эти достижимые точки.

    min = float('inf')

    for i in range(l + 1, h + 1):

        if (i < l + arr[l] + 1):

            jumps = minJumps(arr, i, h)

            if (jumps != float('inf') and 

                       jumps + 1 < min):

                min = jumps + 1

  

    return min

  
# Программа драйвера для проверки вышеуказанной функции

arr = [1, 3, 6, 3, 2, 3, 6, 8, 9, 5]

n = len(arr)

print('Minimum number of jumps to reach',

     'end is', minJumps(arr, 0, n-1))

  
# Этот код предоставлен Soumen Ghosh

C #

// C # программа для поиска минимума
// количество прыжков до конца

using System;

  

class GFG {

    // Возвращает минимальное количество

    // прыгает, чтобы достичь arr [h] от arr [l]

    static int minJumps(int[] arr, int l, int h)

    {

        // Базовый случай: когда источник

        // и пункт назначения одинаков

        if (h == l)

            return 0;

  

        // Когда ничего не достижимо

        // из данного источника

        if (arr[l] == 0)

            return int.MaxValue;

  

        // Обход всех точек

        // достижимо из arr [l]. Рекурсивный

        // получаем минимальное количество прыжков

        // необходимо достичь arr [h] из этих

        // достижимые точки.

        int min = int.MaxValue;

        for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {

            int jumps = minJumps(arr, i, h);

            if (jumps != int.MaxValue && jumps + 1 < min)

                min = jumps + 1;

        }

        return min;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };

        int n = arr.Length;

        Console.Write("Minimum number of jumps to reach end is "

                      + minJumps(arr, 0, n - 1));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// php программа для поиска минимума
// количество прыжков до конца

  
// Возвращает минимальное количество прыжков
// достичь arr [h] из arr [l]

function minJumps($arr, $l, $h)

{

      

    // Базовый случай: когда источник и

    // пункт назначения одинаков

    if ($h == $l)

        return 0;

      

    // Когда ничего не достижимо

    // из данного источника

    if ($arr[$l] == 0)

        return INT_MAX;

      

    // Обход всех точек

    // достижимо из arr [l]. Рекурсивный

    // получаем минимальное количество прыжков

    // необходимо достичь arr [h] из этих

    // достижимые точки.

    $min = 999999;

      

    for ($i = $l+1; $i <= $h && 

             $i <= $l + $arr[$l]; $i++)

    {

        $jumps = minJumps($arr, $i, $h);

          

        if($jumps != 999999 && 

                     $jumps + 1 < $min)

            $min = $jumps + 1;

    }

      

    return $min;

}

  
// Программа драйвера для проверки вышеуказанной функции

$arr = array(1, 3, 6, 3, 2, 3, 6, 8, 9, 5);

$n = count($arr);

  

echo "Minimum number of jumps to reach "

     . "end is ". minJumps($arr, 0, $n-1);

      
// Этот код предоставлен Sam007
?>


Выход:

Minimum number of jumps to reach end is 4

Если мы проследим выполнение этого метода, мы увидим, что будут возникать перекрывающиеся подзадачи. Например, minJumps (3, 9) будет вызываться два раза, так как arr [3] достижим из arr [1] и arr [2]. Таким образом, эта проблема имеет оба свойства ( оптимальная подструктура и перекрывающиеся подзадачи ) динамического программирования.

Метод 2 (динамическое программирование)
В этом методе мы строим массив jumps [] слева направо так, что jumps [i] указывает минимальное количество переходов, необходимое для достижения arr [i] из arr [0]. Наконец, мы возвращаем прыжки [n-1].

C ++

// C ++ программа для минимального количества прыжков до конца
#include <bits/stdc++.h>

using namespace std;

  

int min(int x, int y) { return (x < y) ? x : y; }

  
// Возвращает минимальное количество прыжков
// достичь arr [n-1] из arr [0]

int minJumps(int arr[], int n)

{

    // прыжки [n-1] будут содержать результат

    int* jumps = new int[n];

    int i, j;

  

    if (n == 0 || arr[0] == 0)

        return INT_MAX;

  

    jumps[0] = 0;

  

    // Находим минимальное количество прыжков для достижения arr [i]

    // из arr [0] и присваиваем это значение jumps [i]

    for (i = 1; i < n; i++) {

        jumps[i] = INT_MAX;

        for (j = 0; j < i; j++) {

            if (i <= j + arr[j] && jumps[j] != INT_MAX) {

                jumps[i] = min(jumps[i], jumps[j] + 1);

                break;

            }

        }

    }

    return jumps[n - 1];

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 3, 6, 1, 0, 9 };

    int size = sizeof(arr) / sizeof(int);

    cout << "Minimum number of jumps to reach end is " << minJumps(arr, size);

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

#include <limits.h>
#include <stdio.h>

  

int min(int x, int y) { return (x < y) ? x : y; }

  
// Возвращает минимальное количество переходов для достижения arr [n-1] из arr [0]

int minJumps(int arr[], int n)

{

    int jumps[n]; // прыжки [n-1] будут содержать результат

    int i, j;

  

    if (n == 0 || arr[0] == 0)

        return INT_MAX;

  

    jumps[0] = 0;

  

    // Находим минимальное количество прыжков для достижения arr [i]

    // из arr [0] и присваиваем это значение jumps [i]

    for (i = 1; i < n; i++) {

        jumps[i] = INT_MAX;

        for (j = 0; j < i; j++) {

            if (i <= j + arr[j] && jumps[j] != INT_MAX) {

                jumps[i] = min(jumps[i], jumps[j] + 1);

                break;

            }

        }

    }

    return jumps[n - 1];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 1, 3, 6, 1, 0, 9 };

    int size = sizeof(arr) / sizeof(int);

    printf("Minimum number of jumps to reach end is %d ", minJumps(arr, size));

    return 0;

}

Джава

// JAVA-код для минимального количества прыжков до конца

class GFG {

  

    private static int minJumps(int[] arr, int n)

    {

        int jumps[] = new int[n]; // прыжки [n-1] будут содержать

        // результат

        int i, j;

  

        if (n == 0 || arr[0] == 0)

            return Integer.MAX_VALUE; // если первый элемент равен 0,

        // конец не может быть достигнут

  

        jumps[0] = 0;

  

        // Находим минимальное количество прыжков для достижения arr [i]

        // из arr [0] и присваиваем это значение jumps [i]

        for (i = 1; i < n; i++) {

            jumps[i] = Integer.MAX_VALUE;

            for (j = 0; j < i; j++) {

                if (i <= j + arr[j] && jumps[j] != Integer.MAX_VALUE) {

                    jumps[i] = Math.min(jumps[i], jumps[j] + 1);

                    break;

                }

            }

        }

        return jumps[n - 1];

    }

  

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int arr[] = { 1, 3, 6, 1, 0, 9 };

  

        System.out.println("Minimum number of jumps to reach end is : " + minJumps(arr, arr.length));

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python3 программа для поиска минимума
# количество прыжков до конца

  
# Возвращает минимальное количество прыжков
# достичь arr [n-1] из arr [0]

def minJumps(arr, n):

    jumps = [0 for i in range(n)]

  

    if (n == 0) or (arr[0] == 0):

        return float('inf')

  

    jumps[0] = 0

  

    # Найти минимальное количество

    # прыгает, чтобы достичь arr [i] из

    # arr [0] и назначьте это

    # значение для прыжков [i]

    for i in range(1, n):

        jumps[i] = float('inf')

        for j in range(i):

            if (i <= j + arr[j]) and (jumps[j] != float('inf')):

                jumps[i] = min(jumps[i], jumps[j] + 1)

                break

    return jumps[n-1]

  
Программа # Driver для проверки вышеуказанной функции

arr = [1, 3, 6, 1, 0, 9]

size = len(arr)

print('Minimum number of jumps to reach',

      'end is', minJumps(arr, size))

  
# Этот код предоставлен Soumen Ghosh

C #

// Код C # для минимального количества прыжков для достижения конца

using System;

  

class GFG {

    static int minJumps(int[] arr, int n)

    {

        // прыжки [n-1] будут содержать

        // результат

        int[] jumps = new int[n];

  

        // если первый элемент равен 0,

        if (n == 0 || arr[0] == 0)

  

            // конец не может быть достигнут

            return int.MaxValue;

  

        jumps[0] = 0;

  

        // Находим минимальное количество

        // прыгает, чтобы достичь arr [i]

        // из arr [0] и присваиваем

        // это значение для jumps [i]

        for (int i = 1; i < n; i++) {

            jumps[i] = int.MaxValue;

            for (int j = 0; j < i; j++) {

                if (i <= j + arr[j] && jumps[j] != int.MaxValue) {

                    jumps[i] = Math.Min(jumps[i], jumps[j] + 1);

                    break;

                }

            }

        }

        return jumps[n - 1];

    }

  

    // Драйвер программы

    public static void Main()

    {

        int[] arr = { 1, 3, 6, 1, 0, 9 };

        Console.Write("Minimum number of jumps to reach end is : " + minJumps(arr, arr.Length));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP код для минимального количества
// прыгает до конца

  
// Возвращает минимальное количество прыжков
// достичь arr [n-1] из arr [0]

function minJumps($arr, $n)

{

    // прыжки [n-1]

    // держим результат

    $jumps = array($n);

      

    if ($n == 0 || $arr[0] == 0)

        return 999999;

  

    $jumps[0] = 0;

  

    // Находим минимальное количество

    // прыгает, чтобы достичь arr [i]

    // из arr [0] и присваиваем

    // это значение для jumps [i]

    for ($i = 1; $i < $n; $i++)

    {

        $jumps[$i] = 999999;

        for ($j = 0; $j < $i; $j++)

        {

            if ($i <= $j + $arr[$j] && 

                $jumps[$j] != 999999)

            {

                $jumps[$i] = min($jumps[$i], 

                             $jumps[$j] + 1);

                break;

            }

        }

    }

    return $jumps[$n-1];

}

  

    // Код драйвера

    $arr = array(1, 3, 6, 1, 0, 9);

    $size = count($arr);

    echo "Minimum number of jumps to reach end is "

                             minJumps($arr, $size);

                               
// Этот код предоставлен Sam007
?>


Выход:

Minimum number of jumps to reach end is 3

Спасибо параграфам за предложение этого метода.

Сложность времени: O (n ^ 2)

Метод 3 (динамическое программирование)
В этом методе мы строим массив jumps [] справа налево так, что jumps [i] указывает минимальное количество переходов, необходимое для достижения arr [n-1] из arr [i]. Наконец, мы возвращаем arr [0].

C ++

// Программа CPP для поиска минимума
// количество прыжков до конца
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает минимальное количество
// прыгает до конца

int minJumps(int arr[], int n)

{

    // прыжки [0] будут содержать результат

    int* jumps = new int[n];

    int min;

  

    // Минимальное количество необходимых прыжков

    // чтобы добраться до последнего элемента из последнего

    // элементы сами по себе всегда 0

    jumps[n - 1] = 0;

  

    // Начнем со второго элемента,

    // двигаться справа налево и

    // создаем массив jumps [], где

    // jumps [i] представляет минимальное число

    // прыжков, необходимых для достижения

    // arr [m-1] из arr [i]

    for (int i = n - 2; i >= 0; i--) {

        // Если arr [i] равно 0, то arr [n-1]

        // отсюда невозможно добраться

        if (arr[i] == 0)

            jumps[i] = INT_MAX;

  

        // Если мы можем напрямую добраться до

        // конечная точка отсюда

        // прыжки [я] равен 1

        else if (arr[i] >= n - i - 1)

            jumps[i] = 1;

  

        // В противном случае, чтобы узнать минимум

        // количество прыжков, необходимое для достижения

        // arr [n-1], проверить все точки

        // доступны отсюда и прыжки []

        // значение для этих точек

        else {

            // инициализируем минимальное значение

            min = INT_MAX;

  

            // следующий цикл проверяет все

            // достижимые точки и взятия

            // минимум

            for (int j = i + 1; j < n && j <= arr[i] + i; j++) {

                if (min > jumps[j])

                    min = jumps[j];

            }

  

            // Обработка переполнения

            if (min != INT_MAX)

                jumps[i] = min + 1;

            else

                jumps[i] = min; // или INT_MAX

        }

    }

  

    return jumps[0];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = { 1, 3, 6, 1, 0, 9 };

    int size = sizeof(arr) / sizeof(int);

    cout << "Minimum number of jumps to reach"

         << " end is " << minJumps(arr, size);

    return 0;

}

Джава

// Java программа для поиска минимума
// количество прыжков до конца

class GFG {

    // Возвращает минимальное число

    // прыжков до конца

    static int minJumps(int arr[],

                        int n)

    {

        // прыжки [0]

        // держим результат

        int[] jumps = new int[n];

        int min;

  

        // Минимальное количество прыжков

        // нужно, чтобы достичь последнего

        // элемент из последних элементов

        // само по себе всегда 0

        jumps[n - 1] = 0;

  

        // Начинаем со второго

        // элемент, двигаться справа

        // влево и построить

        // массив jumps [], где jumps [i]

        // представляет минимальное количество

        // прыжки, необходимые для достижения arr [m-1]

        // из обр [я]

        for (int i = n - 2; i >= 0; i--) {

            // Если arr [i] равно 0, то arr [n-1]

            // отсюда невозможно добраться

            if (arr[i] == 0)

                jumps[i] = Integer.MAX_VALUE;

  

            // Если мы можем напрямую добраться до

            // конечная точка отсюда

            // прыжки [я] равен 1

            else if (arr[i] >= n - i - 1)

                jumps[i] = 1;

  

            // В противном случае, чтобы узнать

            // минимальное количество

            // прыжки, необходимые для достижения

            // arr [n-1], проверить все

            // точки достижимы от

            // здесь и прыжки [] значение

            // для этих точек

            else {

                // инициализируем минимальное значение

                min = Integer.MAX_VALUE;

  

                // следующие проверки цикла

                // со всеми достижимыми точками

                // и берет минимум

                for (int j = i + 1; j < n && j <= arr[i] + i; j++) {

                    if (min > jumps[j])

                        min = jumps[j];

                }

  

                // Обработка переполнения

                if (min != Integer.MAX_VALUE)

                    jumps[i] = min + 1;

                else

                    jumps[i] = min; // или Integer.MAX_VALUE

            }

        }

  

        return jumps[0];

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int[] arr = { 1, 3, 6, 1, 0, 9 };

        int size = arr.length;

        System.out.println("Minimum number of"

                           + " jumps to reach end is " + minJumps(arr, size));

    }

}

  
// Этот код предоставлен mits.

python3

# Python3 progrma для поиска минимума
# количество прыжков до конца

  
# Возвращает минимальное количество
# прыгает до конца

def minJumps(arr, n):

      

    # jumps [0] будет содержать результат

    jumps = [0 for i in range(n)] 

  

    # Минимальное количество необходимых прыжков

    # чтобы добраться до последнего элемента из

    # последний элемент сам по себе всегда 0

    # jumps [n-1] также устанавливается в 0

  

    # Начнем со второго элемента,

    # двигаться справа налево и

    # построить массив jumps [] где

    # jumps [i] представляет минимальное число

    Количество прыжков, необходимых для достижения обр [м-1]

    # form arr [i]

    for i in range(n-2, -1, -1):

          

        # Если arr [i] равно 0, то arr [n-1]

        # не может быть достигнуто отсюда

        if (arr[i] == 0):

            jumps[i] = float('inf')

  

        # Если мы можем напрямую связаться с

        # конечная точка отсюда

        # прыжки [я] равен 1

        elif (arr[i] >= n - i - 1):

            jumps[i] = 1

  

        # В противном случае, чтобы узнать

        # минимальное количество прыжков

        # необходимо достичь arr [n-1],

        # проверить все точки

        # можно добраться отсюда и

        # jumps [] значение для этих точек

        else:

            # инициализировать минимальное значение

            min = float('inf'

  

            # следующий цикл проверяет с помощью

            # все точки достижения и

            # занимает минимум

            for j in range(i + 1, n):

                if (j <= arr[i] + i):

                    if (min > jumps[j]):

                        min = jumps[j]

                          

            # Обработка переполнения

            if (min != float('inf')):

                jumps[i] = min + 1

            else:

                # или INT_MAX

                jumps[i] = min 

  

    return jumps[0]

  
# Программа драйвера для проверки вышеуказанной функции

arr = [1, 3, 6, 3, 2, 3, 6, 8, 9, 5]

n = len(arr)

print('Minimum number of jumps to reach',

      'end is', minJumps(arr, n-1))

        
# Этот код предоставлен Soumen Ghosh

C #

// C # программа для поиска минимума
// количество прыжков до конца

using System;

  

class GFG {

    // Возвращает минимальное число

    // прыжков до конца

    public static int minJumps(int[] arr, int n)

    {

        // прыжки [0]

        // держим результат

        int[] jumps = new int[n];

        int min;

  

        // Минимальное количество прыжков, необходимое для

        // достичь последнего элемента из последних элементов

        // само по себе всегда 0

        jumps[n - 1] = 0;

  

        // Начать со второго элемента, переместить

        // справа налево и построить

        // массив jumps [], где jumps [i] представляет

        // минимальное количество прыжков, необходимое для достижения

        // arr [m-1] из arr [i]

        for (int i = n - 2; i >= 0; i--) {

            // Если arr [i] равно 0, то arr [n-1]

            // отсюда невозможно добраться

            if (arr[i] == 0) {

                jumps[i] = int.MaxValue;

            }

  

            // Если мы можем напрямую дойти до конца

            // точка отсюда, прыжки [я] равен 1

            else if (arr[i] >= n - i - 1) {

                jumps[i] = 1;

            }

  

            // В противном случае, чтобы узнать минимум

            // количество прыжков, необходимое для достижения

            // arr [n-1], проверить все точки

            // достижимо отсюда и значение jumps []

            // для этих точек

            else {

                // инициализируем минимальное значение

                min = int.MaxValue;

  

                // следующий цикл проверяет все

                // достижимые точки и занимает минимум

                for (int j = i + 1; j < n && j <= arr[i] + i; j++) {

                    if (min > jumps[j]) {

                        min = jumps[j];

                    }

                }

  

                // Обработка переполнения

                if (min != int.MaxValue) {

                    jumps[i] = min + 1;

                }

                else {

                    jumps[i] = min; // или Integer.MAX_VALUE

                }

            }

        }

  

        return jumps[0];

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        int[] arr = new int[] { 1, 3, 6, 1, 0, 9 };

        int size = arr.Length;

        Console.WriteLine("Minimum number of"

                          + " jumps to reach end is " + minJumps(arr, size));

    }

}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// PHP программа для поиска минимума
// количество прыжков до конца

  
// Возвращает минимальное количество прыжков
// достигнуть конца

function minJumps($arr, $n)

    // прыжки [0] будут содержать результат

    $jumps[$n] = array(); 

    $min;

  

    // Минимальное количество необходимых прыжков

    // чтобы добраться до последнего элемента из последнего

    // элементы сами по себе всегда 0

    $jumps[$n-1] = array(0);

  

    // Начнем со второго элемента,

    // двигаться справа налево и

    // создаем массив jumps [], где

    // jumps [i] представляет минимальное число

    // прыжков, необходимых для достижения

    // arr [m-1] из arr [i]

    for ($i = $n - 2; $i >= 0; $i--)

    {

        // Если arr [i] равно 0, то arr [n-1]

        // отсюда невозможно добраться

        if ($arr[$i] == 0)

            $jumps[$i] = PHP_INT_MAX;

  

        // Если мы можем напрямую добраться до

        // конечная точка отсюда

        // прыжки [я] равен 1

        else if ($arr[$i] >= ($n - $i) - 1)

            $jumps[$i] = 1;

  

        // В противном случае, чтобы узнать минимум

        // количество прыжков, необходимое для достижения

        // arr [n-1], проверить все точки

        // доступны отсюда и прыжки []

        // значение для этих точек

        else

        

            // инициализируем минимальное значение

            $min = PHP_INT_MAX; 

  

            // следующий цикл проверяет все

            // достижимые точки и взятия

            // минимум

            for ($j = $i + 1; $j < $n &&

                 $j <= $arr[$i] + $i; $j++)

            {

                if ($min > $jumps[$j])

                    $min = $jumps[$j];

            

  

            // Обработка переполнения

            if ($min != PHP_INT_MAX)

                $jumps[$i] = $min + 1;

            else

                $jumps[$i] = $min; // или INT_MAX

        }

    }

  

    return $jumps[0];

}

  
// Код драйвера

$arr = array(1, 3, 6, 1, 0, 9);

$size = sizeof($arr);

echo "Minimum number of jumps to reach",

     " end is ", minJumps($arr, $size);

  
// Этот код предоставлен ajit.
?>


Выход:

Minimum number of jumps to reach end is 3

Сложность времени: O (n ^ 2) в худшем случае.

Минимальное количество прыжков для достижения конца | Набор 2 (O (n) решение)

Спасибо Ашишу за предложение этого решения.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальное количество прыжков для достижения конца

0.00 (0%) 0 votes