Рубрики

Программа PHP для минимального количества прыжков, чтобы достичь конца

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

<?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

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

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

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

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

Программа PHP для минимального количества прыжков, чтобы достичь конца

0.00 (0%) 0 votes