0

我正在解决一个练习问题并且被卡住了。该问题要求编写一个方法，该方法接受两个整数 x 和 y，通过重复使用三个移动之一来打印在 2D 平面中从 (0,0) 到 (x,y) 的所有解决方案：

  • 向右移动 1 (E)
  • 向上移动 1 (N)
  • 向右移动 1 和向上 1 (NE)

这些是一些示例调用：

  • 通话：旅行（2、1）
  • 输出： EEN // ENE // E NE // NEE // 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）；
  • 输出：EEN // NE // NE // NEE // NE E

我知道对于这个示例调用，问题在于 E 仅在需要 E 的三种不同情况下打印一次，因为 E 是在调用后续递归方法之前打印的。

我想通过在每次调用 travel 方法时附加 System.out.print 命令来解决这个问题（不确定这是正确的方法）。这样，每当调用 travel 方法时，每次都会以第一个字母打印结果。但是，由于该方法不返回任何内容，因此我无法在 print 语句中插入该方法。这是我被困了很长时间的地方。

任何有关如何从这里开始的建议将不胜感激。

4

1 回答 1

2

在递归构建解决方案时，通常将部分构建的解决方案作为参数传递给递归调用。

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每条路径都只有一次调用。

于 2013-06-24T19:24:59.010 回答