0

我正在为一个班级做一个java作业，但我不确定如何解决这个问题。我不希望它为我完成，但让我朝着正确的方向开始。我主要不确定程序的递归部分。我不太擅长编程。

问题：

东北路径是通过向上和向右移动从二维网格获得的。例如，在下图中，从 1,0 到 0,1 有两条路径。第一个是（1,0），（0,0），（0,1），第二个是（1,0），（1,1），（0,1）。请注意，没有从 (0,1) 到任何其他点的东北路径。另请注意，从 (1,1) 到 (0,1) 有一条东北路径。您将编写一个程序，该程序需要一个数字（网格大小 - 不大于 10）以及一个起始位置和一个结束位置，并递归计算所有“NorthEast”路径。

0,0 0,1

1,0 1,1

我正在阅读 prog2.dat 文件

它首先读取网格大小，然后是起始坐标，然后是完成坐标。例如：

5

3 0

1 3

它需要是一个文件，所以我将使用方法。如果有人可以让我开始或指导我解决已经发布的类似问题，我将不胜感激。

4

3 回答 3

0

这可能会有所帮助：

http://en.wikipedia.org/wiki/Binomial_theorem

于 2010-02-09T19:22:48.063 回答
0

从阅读帕斯卡三角开始。

对于给定的起始位置 (x0, y0) 和给定的结束位置 (x1, y1)，并限制自己在网格上向北或向东移动，最小长度路径将精确地由 (x1-x0) 步骤组成以某种顺序向东和（y1-y0）向北迈进。

于 2010-02-09T19:34:17.310 回答
0

涉及递归的一种解决方案涉及找到路径上的下一个点，该点将使您最接近目的地。一旦你有了那个点，你就可以使用相同的方法来找出下一个最近的点，依此类推。当您到达目的地时，此过程（或递归）结束。

你可以尝试做这样的事情：

void getNextPoint(Point start, Point end, Path currentPath) {
    //if start == end, then you're done with the recursion
    //and you have a valid path

    //if you can move east from start to get closer to end
    //Point next = east of start
    //append next to the currentPath
    //then call getNextPoint(next, end, currentPath)

    //if you can move north from start to get closer to end
    //Point next = north of start
    //append next to currentPath
    //then call getNextPoint(next, end, currentPath)
}

我省略了很多细节，所以你可以自己弄清楚，但这是使用递归的一种方法。本质上，您正在构建一条路径。你必须弄清楚如何管理你的路径，但你可能需要能够从它们中推送和弹出点。

于 2010-02-09T19:49:32.373 回答