代码之家 › 专栏 › 技术社区 › Sheng.Zh

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

towers-of-hanoi stack java

Sheng.Zh · 技术社区 · 7 年前

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;

动作记录=动作。不记录=nowAct; 然后代码无法运行。

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

1 回复 | 直到 7 年前

Steven Jeffries 7 年前

record 被定义为数组,因为其值在 fStackTotStack 方法

,而不是参考 . 它也按值传递对象引用。

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

这是因为 bar foo 函数与 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的bar与main的bar不同。

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

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

酒吧 变量和主变量变量是不同的变量,它们指向相同的底层对象。因此,对对象本身(而不仅仅是变量)的更改将持续。

在上面的示例中,行 Action[] record = { Action.No }; 正在创建传递到 fStackTotStack公司 方法由于变量 记录 record = new Action[] {} 它指向的数组仍然与传递的数组相同。这意味着您可以对对象本身(在本例中为数组)进行更改。

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