A frog is trying to cross a pond but he can only jumps on stones and he can jump up to five units.
We have been given an array with ones and zeros (zeros for water and ones for stones) and the task to find the best possible approach to find the path with the least number of jump(using divide and conquer if possible).
Example for array -> [0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0] p.s: the frog starts one unit before the array and have to reach a unit after the array (it is possible that there is no path available with conditions mentioned)
I'm just starting to learn algorithms so it would be nice if you guys help me with the algorithm and code.
My idea for a divide and conquer approach would be the following:
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.
Let's use your given array as an example: [0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0]
[0 0 0 1 0 0 1 0 0 1|0 1 0 0 1 0 1 1 0 0 0 0][0 0 0 1|0 0 1 0 0 1|0 1 0 0 1|0 1 1 0 0 0 0][0 0 0 1|0 0 1|0 0 1|0 1 0 0 1|0 1 1|0 0 0 0]In this case, the frog would jump to the first, the second, the third, the fifth, and the seventh 1 before reaching the goal (= 6 jumps).
Why does this algorithm work? Let's assume, it wouldn't output a shortest way of jumping for the frog. That would mean, we didn't find the partialArrays with the largest jumps for the frog. If one partialArray wouldn't resemble a largest jump, that would mean: There would be at least one 1 after the 1 inside the partialArray which the frog can still reach. This isn't possible, since length(partialArray) ≤ 5 holds. Thus, every 1 after the partialArray would be too far away (> 5).