Рубрики

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

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

#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;

}

Выход:

Minimum number of jumps to reach end is 4

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

C / C ++

#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 = new int[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;

}

Выход:

Minimum number of jumps to reach end is 3

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

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

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

0.00 (0%) 0 votes