我如何通过这个编程面试问题 [英] How do I get through this programming interview question

问题描述

给出一个二维矩阵，其中1表示青蛙可以跳跃的地方，0代表空的空间，青蛙可以在水平方向上自由移动（仅在1的位置），而不会产生任何费用（跳跃）。垂直跳跃矩阵的给定点到矩阵上的另一个点可以采用（仅在1），成本为跳跃次数。鉴于来源和目的地，青蛙必须到达目的地，最大限度地降低成本（跳跃）。



我尝试过：



我曾尝试从第一个单元格开始，检查行中是否有相邻的1。如果然后移动到它，否则向下移动。但是，似乎问题需要一些不同的方法

given a 2 D matrix where 1 represent the places where the frog can jump and 0 represent the empty spaces, the frog can move freely in horizontal direction (on 1’s only) without incurring any cost (jump).A vertical jump from a given point of the matrix to another point on the matrix can be taken (on 1’s only) with cost as the number of jumps taken. Given a source and destination, the frog has to reach the destination minimizing the cost (jump).

What I have tried:

I had tried to start from the first cell and check whether any adjacent 1 is there in the row. If there then move to it, else move downwards. However, it seems, the question requires some different approach

推荐答案

作为程序员，你的工作是创建算法来解决具体问题，这个是他们想要测试的能力。

创建算法基本上是找到数学并进行必要的调整以适应你的实际问题。



它有助于掌握一些分析方法， Dijkstra自上而下方法是一个良好的开端。

https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design [ ^ ]

https ：//en.wikipedia.org/wiki/Structured_programming [ ^ ]

https://en.wikipedia.org/wiki/Edsger_W._Dijkstra [ ^ ]

https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF [ ^ ]

As programmer, your job is to create algorithms that solve specific problems, this is the ability they want to test.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

It mat help to master some analyze methods, Dijkstra Top-Down method is a good start.
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
https://en.wikipedia.org/wiki/Structured_programming[^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]

这是一个优化算法，如果你需要一个起点，然后看看这个维基百科页面：数学优化 - 维基百科 [ ^ ]。

It is an optimization algorithm, if you need a starting point, then look at this Wikipedia page: Mathematical optimization - Wikipedia[^].

首先，您需要一个算法来查找所有有用的路径和存储它们。一种简单的方法是使用一种算法，将距离矢量最小化为零。



根据墙壁或障碍物，它可能不是最短路径，而是围绕它们。因此，靠近障碍物的点可能是目标的阶段。



之后，您评估每条路径的成本，找到最佳路径（以最低成本）。 br $>




制作一些图纸以显示问题。

At first you need an algorithm to find all useful pathes and stores them. A simple approach is to use a algorithm which minizes the distance vector to zero.

Depending on walls or obstacles it may not be the shortest path, but around them. So point near the obstacles may be stages to the goal.

After that you rate the costs of every path, to find the optimal path (with minimal cost).


Make some drawings to visualize the problem.

这篇关于我如何通过这个编程面试问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！