问求数组中最小数路径的递归法
EN

Stack Overflow用户

提问于 2015-10-21 12:03:50

回答 1查看 669关注 0票数 2

我有数组[0,1,3,4,1]。使用这个数组，我需要编写一个递归函数，它要么是：

转到下一个元素，或者
跳过下一个元素，然后转到后面的元素(只能跳过最多为1个元素)。

条件是它必须是尽可能小的数目。解决这一问题的办法如下：

从0开始
跳过1并转到3
跳过4并转到1
添加未跳过的元素并返回它

我已经从它的基本情况开始了这个函数：

private int play(int[] a, int first, int last) {
    int result = 0;

    // base case
    if (first == last){
        return a[first];
    }
    else{
        //result = play(a,first+1,last);
        //System.out.println(result);
    }
    return result;

}

first = 0和last = array_length -1。注意，数组可以有任意数量的元素，所以如果我有数组[0 4 23 566 34 45 555 11 34 35 45 65 55 98 344]，最低的总数将是591。

请容忍我，我对这种递归的东西是新的。提前感谢

java

arrays

recursion

腾讯云会员中心

加入腾讯云会员，每月可领会员专属优惠券；会员云产品免费体验；云产品会员专享价；会员签到抽奖…

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-10-21 12:32:13

我会这样做，您可以跟踪当前的索引，以及到目前为止，沿着路径的索引的总和(所以求和将不包括我们跳过的数字)。

public static int play(int[] a, int index, int sum){
    if (index>=a.length) return Integer.MAX_VALUE;  //Path went over last index. Invalid Path. 
    sum += a[index];  //Add on to the sum of the index you are currently on
    if (index == a.length-1){
        return sum;  //If we are at last element, return sum of the path traveled
    }else{
        return Math.min(play(a, index+1, sum), play(a, index+2, sum)); //Continue onto path checking both options
    }
}

测试代码：

public static void main(String args[]) {
    int[] a = new int[]{0, 4, 23, 566, 34, 45, 555, 11, 34, 35, 45, 65, 55, 98, 344};
    System.out.println(play(a, 0, 0));
}

输出：591

希望这能有所帮助。

编辑:好的，删除所有的代码，然后在逻辑上考虑这一点。我认为递归(尤其是路径)的方式是，我派遣个别的小人物，在每次递归之后，我将复制那些小人物，以选择不同的路径。让我们在本例中使用较小的数组[0,1,3,4,1]。

我们从一个小男人开始。他从0开始。他有两个选择。第一个选项是转到1，第二个选项是去3。我们需要走这两条路，因为我们不确定前面有什么。这个小个子男人重复自己把一个人送去1，另一个人去3。

现在，走到小路上的小个子1还有另外两个选择。他要么去3，要么去4。走到3路上的小个子男人还有另外两个选择。他可以去4或1。所以他们复制了自己，让小人物们完成所有的选择。我希望这一切在这一点上都有意义。处理小人物复制到不同路径的代码是：play(a, index+1, sum), play(a, index+2, sum))

一个小个子人一旦走到路的尽头会做什么？他必须告诉原来的小家伙这条路有多远。其代码是：if (index == a.length-1){return sum;}

不过，最初的小个子并不在乎这条路。他需要和走另一条路的人比较，看看哪条比较短。这是由Math.Min控制的。只返回两个小个子男人的较短距离。因此，距离越短的小人就会杀死他的克隆人(:p)，因为我们不喜欢这条路。最后，所有的小人物都会互相残杀，只剩下一个小个子站着，这是最短的距离。:)

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/33268230

复制

【数据库报错（未删除任何行，未更新任何行）】

数据库 null 表格数据数据类型

首先查看定义的表格数据类型有无问题，点击表格编辑前100行如何更改编辑行数：更改编辑行数这里的允许NULL值为通过输入端输入后，写进数据库是否包含空值例如，输入端通过注册输入注册名后，若允许NULL值未勾选，则写进表格的为用户名+数据类型除了用户名所占字节剩余用空格进行填充（写入表格中的数据为用户名+若干空格）若允许NULL值勾选了，则写进表格的即为刚刚进行注册的用户名，其后没有多余空格

magize

2023/07/11