我正在解决一道练习题,但遇到了困难。该问题要求编写一个方法,该方法接受两个整数 x 和 y,通过重复使用三个移动之一来打印在 2D 平面中从 (0,0) 到 (x,y) 行进的所有解决方案:
- 向右移动 1 (E)
- 向上移动 1 (N)
- 向右移动 1 并向上移动 1(NE)
这些是一些示例调用:
- 调用:旅行(2, 1)
- 输出:E E N//E N E//E NE//N E E//NE E
我编写了以下代码:
public void travel(int x, int y) {
if (x == 0 && y == 0) {
System.out.println();
} else if (x > 0 && y > 0) {
System.out.print("E ");
travel(x-1, y);
System.out.print("N ");
travel(x, y-1);
System.out.print("NE ");
travel(x-1, y-1);
} else if (x > 0 && y == 0) {
System.out.print("E ");
travel(x-1, y);
} else if (y > 0 && x == 0) {
System.out.print("N ");
travel(x, y-1);
}
}
调用上述方法会产生以下代码:
- 调用:旅行(2,1);
- 输出:E E N//N E//NE//N E E//NE E
我知道对于这个示例调用,问题在于 E 仅在需要 E 的三种不同情况下打印一次,因为 E 是在调用后续递归方法之前打印的。
我想通过在每次调用 Travel 方法时附加 System.out.print 命令来解决此问题(不确定这是正确的方法)。这样,每当调用旅行方法时,每次都会打印结果的第一个字母。但是,由于该方法不返回任何内容,因此我无法在 print 语句中插入该方法。这是我被困了很长时间的地方。
任何关于如何从这里开始的建议将不胜感激。
最佳答案
递归构建解决方案时,通常会将部分构建的解决方案作为参数传递给递归调用。
public void travel(int x, int y, String path) {
if (x == 0 && y == 0) {
System.out.println(path);
} else if (x > 0 && y > 0) {
travel(x-1, y, path + ' E');
travel(x, y-1, path + ' N');
travel(x-1, y-1, path + ' NE');
} else if (x > 0 && y == 0) {
travel(x-1, y, path + ' E');
} else if (y > 0 && x == 0) {
travel(x, y-1, path + ' N');
}
}
看看我们如何在前进时构建路径 - 并让函数调用处理记住我们在搜索中的位置的复杂性?这还有一个好处就是可以简化我们的代码,因为每个路径我们只调用一次 System.out.println
。
关于java - 基本递归回溯(机器人二维寻路),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17283348/