使用分而治之法找到青蛙穿越池塘的跳跃次数最少的路径

Question

一只青蛙正试图穿过池塘，但他只能在石头上跳跃，他最多可以跳五个单位。

我们得到了一个包含 1 和 0 的数组（0 表示水，1 表示石头）以及寻找最佳方法的任务，以找到跳跃次数最少的路径（如果可能，使用分而治之） ).

数组示例 -> [0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0] p.s：青蛙从数组前一个单位开始，必须到达数组后一个单位（有可能没有条件的路径）

我刚刚开始学习算法，所以如果你们能帮助我完成算法和代码，那就太好了。

Answer 1

我对分而治之方法的想法如下：

program frog(array)
begin
  divide array after the '1' left of the center of the array;
  foreach (partialArray) do begin
    if (length(partialArray) > 5) then frog(partialArray);
  end foreach;
end.

让我们以您给定的数组为例：[0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0]

1^st除法：[0 0 0 1 0 0 1 0 0 1|0 1 0 0 1 0 1 1 0 0 0 0]
2^nd除法：[0 0 0 1|0 0 1 0 0 1|0 1 0 0 1|0 1 1 0 0 0 0]
3^rd除法：[0 0 0 1|0 0 1|0 0 1|0 1 0 0 1|0 1 1|0 0 0 0]

在这种情况下，青蛙会跳到第一个、第二个、第三个、第五个和第七个 1 才到达目标（= 6 次跳跃）。

为什么这个算法有效？让我们假设，它不会为青蛙输出最短的跳跃方式。这意味着，我们没有找到青蛙跳跃最大的 partialArray。如果一个 partialArray 不像最大的跳跃，那将意味着：青蛙仍然可以到达的 partialArray 内的 1 之后至少有一个 1。这是不可能的，因为 length(partialArray) ≤ 5 成立。因此，partialArray 之后的每个 1 都太远了 (> 5)。

使用分而治之法找到青蛙穿越池塘的跳跃次数最少的路径

find the path with least number of jumps for a frog crossing pond using divide and conquer

algorithm

divide-and-conquer