0

我有一个关于递归的小问题。下面的代码实际上是对到达结束的最小跳转次数问题的答案

// 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 && i <= l + arr[l]; i++) {
        int jumps = minJumps(arr, i, h);
        if (jumps != INT_MAX && 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 并且函数结束。否则，它会更新一个名为jumps的变量，但我无法理解该语句。例如，当 i=1 或 i=2 时，jumps 的值是多少等等。换句话说，我无法理解 jumps 变量更新过程的意义。

4

1 回答 1

0

或许关键是要仔细阅读和理解函数的定义：

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

这很清楚。

实现递归函数时的工作是将问题分解为基本案例或案例，以及通过递归调用解决一个或多个较小问题的递归步骤，然后使用结果来解决整体问题。

这里的基本情况是在同一位置开始和结束。不需要任何步骤。返回 0。

（作者还将零数组元素视为一种特殊情况。这是不必要的。如果删除这些行，程序将同样工作。）

递归步骤实现了这个想法：

要从lto ，首先从toh迈出一步，然后（递归地）计算从to的最小步数S。因此总步数为 S+1。liih

选择什么i？找到最少步数的唯一方法是考虑所有可能性并取最小值。这些可能性是l+1through h，即长度为 1 的初始步骤一直到在单个步骤中覆盖从l到的整个间隙h（因此第二步的长度为零）。

于 2021-08-10T02:27:03.143 回答