使用堆栈解决河内塔 (java)

Question

public static enum Action {
    No, LToM, MToL, MToR, RToM
}

public static int hanoiProblem2(int num, String left, String mid, String right) {
    Stack<Integer> lS = new Stack<Integer>();
    Stack<Integer> mS = new Stack<Integer>();
    Stack<Integer> rS = new Stack<Integer>();
    lS.push(Integer.MAX_VALUE);
    mS.push(Integer.MAX_VALUE);
    rS.push(Integer.MAX_VALUE);
    for (int i = num; i > 0; i--) {
        lS.push(i);
    }
    Action[] record = { Action.No };
    int step = 0;
    while (rS.size() != num + 1) {
        step += fStackTotStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
        step += fStackTotStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
        step += fStackTotStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
        step += fStackTotStack(record, Action.MToR, Action.RToM, rS, mS, right, mid);
    }
    return step;
}

public static int fStackTotStack(Action[] record, Action preNoAct,
                                 Action nowAct, Stack<Integer> fStack, Stack<Integer> tStack,
                                 String from, String to) {
    if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
        tStack.push(fStack.pop());
        System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
        record[0] = nowAct;
        return 1;
    }
    return 0;
}

public static void main(String[] args) {
    int num = 4;

    // solution 2
    int steps2 = hanoiProblem2(num, "left", "mid", "right");
    System.out.println("It will move " + steps2 + " steps.");
    System.out.println("===================================");

}

这是解决汉诺塔的代码。它使用三个堆栈来模拟 3 个塔。我的问题是为什么它将记录变量定义为数组？动作[]记录={Action.No}；记录[0] = nowAct;

我试着把它们改成动作记录=Action.No；记录=现在行动；然后代码无法运行.

我不知道原因。如果有人能解释原因，我真的很感激。谢谢

Answer 1

在您的示例中，record 被定义为一个数组，因为它的值在 fStackTotStack 方法中被更改。

最简单的解释是因为 Java 通过 value 传递变量，而不是 reference。它也按值传递对象引用。

以下面的代码为例：

public void foo(int bar) {
  bar += 4;
  System.out.println("Foo's bar: " + bar);
}

public static void main(String[] args) {
  int bar = 5;
  new Foo().foo(bar);
  System.out.println("Main's bar: " + bar);
}

这将打印出：

Foo's bar: 9 
Main's bar: 5

这是因为 foo 函数中的 bar 变量与 main 函数中的变量不同。该值只是在调用方法时复制过来。

传递数组时，变量本身还是不一样的：

public void foo(int[] bar) {
  bar = new int[]{9};
  System.out.println("Foo's bar: " + bar[0]);
}

public static void main(String[] args) {
  int[] bar = {5};
  new Foo().foo(bar);
  System.out.println("Main's bar: " + bar[0]);
}

这将产生与以前相同的结果，因为 foo 的栏与 main 的栏不同。

但是，对象引用是按值传递的。这意味着虽然变量不同，但它们表示的值是相同的。因此：

public void foo(int[] bar) {
  bar[0] += 4;
  System.out.println("Foo's bar: " + bar[0]);
}

public static void main(String[] args) {
  int[] bar = {5};
  new Foo().foo(bar);
  System.out.println("Main's bar: " + bar[0]);
}

将打印出与以前不同的内容：

Foo's bar: 9 
Main's bar: 9

这是因为虽然 foo 的 bar 变量和 main 的 bar 变量是不同的变量，但它们指向相同的底层对象。因此，对对象本身（而不仅仅是变量）的更改将持续存在。

在上面的示例中，行 Action[] record = { Action.No }; 正在创建一个数组，该数组将传递给 fStackTotStack 方法。由于变量 record 本身没有改变（任何地方都没有 record = new Action[] {}），它指向的数组仍然是传递的那个数组。这意味着您可以更改对象本身（在本例中为数组）。

Here is an article that can explain it better than I can.

使用堆栈解决河内塔 (java)

Using stacks to solve tower of Hanoi (java)

java

stack

towers-of-hanoi