Блог

Главная - Вопросы по программированию - Минимальное количество переходов для достижения конечного рекурсивного подхода

Минимальное количество переходов для достижения конечного рекурсивного подхода

#arrays #c #recursion

Вопрос:

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

 // C program to find Minimum
// number of jumps to reach end
#include <limits.h>
#include <stdio.h>

// Returns minimum number of
// jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int l, int h)
{
    // Base case: when source and destination are same
    if (h == l)
        return 0;

    // When nothing is reachable from the given source
    if (arr[l] == 0)
        return INT_MAX;

    // Traverse through all the points
    // reachable from arr[l]. Recursively
    // get the minimum number of jumps
    // needed to reach arr[h] from these
    // reachable points.
    int min = INT_MAX;
    for (int i = l   1; i <= h amp;amp; i <= l   arr[l]; i  ) {
        int jumps = minJumps(arr, i, h);
        if (jumps != INT_MAX amp;amp; jumps   1 < min)
            min = jumps   1;
    }

    return min;
}

// Driver program to test above function
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;
}

Когда h==l и arr[l]==0, функция возвращает sth и функция заканчивается. В противном случае он обновляет переменную, называемую прыжками, но я не могу понять это утверждение. Например, какова величина скачков, когда i=1 или i=2 и так далее. Другими словами, я не могу понять смысл процесса обновления переменной прыжков.

Комментарии:

1. Мне непонятно, в чем заключается ваше сомнение. Я имею в виду… вы заметили, что jumps это присваивается min , когда условие является правильным, а затем min возвращается.

2. Рассматриваемая строка определяет вызываемую переменную jumps и присваивает ей значение, которое является значением, возвращаемым рекурсивным вызовом функции minJumps() . То есть выполняется один и тот же код, но передаются разные параметры. Компилятор реализует эти вызовы таким образом, что для каждого вызова функции точное состояние вызывающей функции запоминается и восстанавливается при возврате этой функции. Я надеюсь, что это немного поможет. (Я должен сказать, что этот пример-не лучший способ изучить рекурсию. дайте мне последовательность Фибоначчи в любой день.)

3. Примечание: старайтесь не использовать строчные l буквы в качестве имени переменной. Это ужасно похоже на номер 1 .

Ответ №1:

Возможно, ключ в том, чтобы внимательно прочитать и понять определение функции:

 // Returns minimum number of
// jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int l, int h)

Это довольно ясно.

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

Базовый вариант здесь начинается и заканчивается в одном и том же месте. Никаких шагов не требуется. Верните 0.

(Автор также рассматривает нулевые элементы массива как особый случай. В этом не было необходимости. Программа работала бы так же, если бы эти строки были удалены.)

Рекурсивный шаг реализует эту идею:

Чтобы перейти от l до h , сначала сделайте один шаг от l до i , а затем (рекурсивно) определите минимальное количество шагов S от i до h . Таким образом, общее количество шагов равно S 1.

Для чего выбирать i ? Единственный способ найти наименьшее количество шагов-это рассмотреть все возможности и выбрать минимальное. Эти возможности l 1 исчерпаны h , т. е. начальный шаг длиной 1 вплоть до покрытия всего промежутка от l до h за один шаг (поэтому второй шаг имеет нулевую длину).

Метки: