数河内塔 -Java

Question

我正在测试河内塔程序。我已经得到了测量程序时间的帮助，但这不是我的教授想要的，他想要计算迭代次数。我无法记下它，我需要我的程序运行的“移动总数”，但它不会正确打印出来。你们能帮帮我吗？谢谢你。

这是我使用的代码：

package Whosebug;

import java.util.*;

public class towers {
    public static int N;
    public static Stack<Integer>[] integer = new Stack[4];

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        integer[1] = new Stack<>();
        integer[2] = new Stack<>();
        integer[3] = new Stack<>();
        System.out.print("Enter 5 integers: ");
        int num = input.nextInt();
        N = num;
        StackMove(num);
    }

    public static void StackMove(int N) {
        for (int d = N; d > 0; d--)
            integer[1].push(d);
        PrintStack();
        move(N, 1, 2, 3);
    }

    public static void move(int N, int a, int b, int c) {
        if (N > 0) {
            move(N - 1, a, c, b);
            int d = integer[a].pop();
            integer[c].push(d);
            PrintStack();
            move(N - 1, b, a, c);
        }
    }

    public static void PrintStack() {
        System.out.println("  A  |  B  |  C");
        System.out.println("---------------");
        for (int i = N - 1; i >= 0; i--) {
            String d1 = " ", d2 = " ", d3 = " ";
            try {
                d1 = String.valueOf(integer[1].get(i));
            } catch (Exception e) {
            }
            try {
                d2 = String.valueOf(integer[2].get(i));
            } catch (Exception e) {
            }
            try {
                d3 = String.valueOf(integer[3].get(i));
            } catch (Exception e) {
            }
            System.out.println("  " + d1 + "  |  " + d2 + "  |  " + d3);
        }
        System.out.print("\n");
    }
}

输出应该是这样的：

Outpu1 Output2

Answer 1

代码

import java.util.Stack;

import java.util.*;

public class TowersOfHanoiPrint {
    public static int N;
    public static Stack<Integer>[] integer = new Stack[4];

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        integer[1] = new Stack<>();
        integer[2] = new Stack<>();
        integer[3] = new Stack<>();
        System.out.print("Enter 5 integers: ");
        int num = input.nextInt();
        N = num;
        System.out.println("Number of moves: "+StackMove(num));
    }

    public static int StackMove(int N) {
        for (int d = N; d > 0; d--)
            integer[1].push(d);
        PrintStack();
        return move(N, 1, 2, 3);
    }

    public static int move(int N, int a, int b, int c) {
        if (N > 0) {
            int numberMovesA = move(N - 1, a, c, b);
            int d = integer[a].pop();
            integer[c].push(d);
            PrintStack();
            int numberMovesB = move(N - 1, b, a, c);
            return (numberMovesA + numberMovesB + 1);
        }
        return 0;
    }

    public static void PrintStack() {
        System.out.println("  A  |  B  |  C");
        System.out.println("---------------");
        for (int i = N - 1; i >= 0; i--) {
            String d1 = " ", d2 = " ", d3 = " ";
            try {
                d1 = String.valueOf(integer[1].get(i));
            } catch (Exception e) {
            }
            try {
                d2 = String.valueOf(integer[2].get(i));
            } catch (Exception e) {
            }
            try {
                d3 = String.valueOf(integer[3].get(i));
            } catch (Exception e) {
            }
            System.out.println("  " + d1 + "  |  " + d2 + "  |  " + d3);
        }
        System.out.print("\n");
    }
}

输出

Enter 5 integers: 6
  A  |  B  |  C
---------------
  1  |     |   
  2  |     |   
  3  |     |   
  4  |     |   
  5  |     |   
  6  |     |   

  A  |  B  |  C
---------------
     |     |   
  2  |     |   
  3  |     |   
  4  |     |   
  5  |     |   
  6  |  1  |   

  A  |  B  |  C
---------------
     |     |   
     |     |   
  3  |     |   
  4  |     |   
  5  |     |   
  6  |  1  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
  3  |     |   
  4  |     |   
  5  |     |  1
  6  |     |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  4  |     |   
  5  |     |  1
  6  |  3  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  4  |     |   
  5  |     |   
  6  |  3  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  4  |     |   
  5  |  2  |   
  6  |  3  |   

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  4  |  1  |   
  5  |  2  |   
  6  |  3  |   

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
  5  |  2  |   
  6  |  3  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  5  |  2  |  1
  6  |  3  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |     |   
  5  |     |  1
  6  |  3  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  5  |     |   
  6  |  3  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  5  |     |  3
  6  |     |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |     |   
  5  |     |  3
  6  |  1  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  2
  5  |     |  3
  6  |  1  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
  5  |     |  3
  6  |     |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
     |     |  3
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  2
  1  |     |  3
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  1  |  2  |  3
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
     |  2  |  3
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
  3  |  2  |   
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  3  |  2  |  1
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |     |   
  3  |     |  1
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  3  |     |   
  6  |  5  |  4

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  3  |  4  |   
  6  |  5  |   

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |  1  |   
  3  |  4  |   
  6  |  5  |   

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
  3  |  4  |   
  6  |  5  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  3  |  4  |  1
  6  |  5  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  3  |   
     |  4  |  1
  6  |  5  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  3  |   
  1  |  4  |   
  6  |  5  |  2

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |  2  |   
     |  3  |   
  1  |  4  |   
  6  |  5  |   

  A  |  B  |  C
---------------
     |     |   
     |  1  |   
     |  2  |   
     |  3  |   
     |  4  |   
  6  |  5  |   

  A  |  B  |  C
---------------
     |     |   
     |  1  |   
     |  2  |   
     |  3  |   
     |  4  |   
     |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |  2  |   
     |  3  |   
     |  4  |  1
     |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  3  |   
     |  4  |  1
  2  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  3  |   
  1  |  4  |   
  2  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  1  |  4  |  3
  2  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
     |  4  |  3
  2  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |  2
     |  4  |  3
     |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
     |  4  |  3
     |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
     |     |  3
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  2
  1  |     |  3
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  1  |  2  |  3
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
     |  2  |  3
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
  3  |  2  |   
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  3  |  2  |  1
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |     |   
  3  |     |  1
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  3  |     |   
  4  |  5  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
  1  |     |   
  2  |     |   
  3  |     |  5
  4  |     |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
  2  |     |   
  3  |     |  5
  4  |  1  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  2
  3  |     |  5
  4  |  1  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
  3  |     |  5
  4  |     |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  2
     |     |  5
  4  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  2
  1  |     |  5
  4  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |   
  1  |  2  |  5
  4  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |   
     |  2  |  5
  4  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |  1  |  4
     |  2  |  5
     |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  4
     |  2  |  5
     |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  1
     |     |  4
     |     |  5
  2  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |   
     |     |  4
  1  |     |  5
  2  |  3  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  3
     |     |  4
  1  |     |  5
  2  |     |  6

  A  |  B  |  C
---------------
     |     |   
     |     |   
     |     |  3
     |     |  4
     |     |  5
  2  |  1  |  6

  A  |  B  |  C
---------------
     |     |   
     |     |  2
     |     |  3
     |     |  4
     |     |  5
     |  1  |  6

  A  |  B  |  C
---------------
     |     |  1
     |     |  2
     |     |  3
     |     |  4
     |     |  5
     |     |  6

Number of moves: 63

Answer 2

对于 n 项，将 2 提高到 n 并减去 1。

Answer 3

题外话评论

这里有一些对您的代码的评论，它们没有解决您的问题，但必须告诉您。（关于下面的主题评论）

标识符的命名

采纳Java Naming Conventions！

例如：

class 名称以大写字母开头，而方法名称以小写字母开头（反之亦然）
变量也以小写字母开头，只有常量是ALL_UPPER_CASE

那就不要对变量使用单字母名称。

在为变量选择名称时，请从问题域中取名。
变量integer是什么意思？
更合适的名称在这里是 stacks（注意复数 's'），但不是因为它包含 Stack class 的对象，而是因为您正在为堆栈建模。

你的(class)成员变量N干扰了一些方法的参数N。这是可以接受违反 Java 命名约定的唯一一点：您可以在成员变量前加上下划线 (_)。这将有效地避免这种干扰。

避免奇怪的球解决方案

这个双重标识符 N 导致您的程序采用两种不同的方法：

你的一些方法访问成员变量N。
其他一些方法具有相同类型和相同名称的参数。

对于任何程序，选择其中一种访问方法。

想象一下如果您需要更改 N 会发生什么。您的程序会开始表现得很奇怪，您将很难找到错误。

不要使用异常作为流程控制

String d1 = " ", d2 = " ", d3 = " ";
try {
    d1 = String.valueOf(integer[1].get(i));
} catch (Exception e) {
}

使用此代码，您可以将 space 保留在 d1 中，以防第一个堆栈没有足够的元素。你最好使用 if 语句来做到这一点：

String d1 = " ", d2 = " ", d3 = " ";
if( i < integer[1].size() ){
    d1 = String.valueOf(integer[1].get(i));
}

这不仅在您的代码中节省了一行，还比您的原始代码更好地传达了您的意图。

使用基于零的索引。

您声明了大小为 4 的数组 integer 以便能够通过自然计数访问其元素

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        integer[1] = new Stack<>();
        integer[2] = new Stack<>();
        integer[3] = new Stack<>();

这里的问题是您在该数组中有一个未使用的附加元素。更糟糕的是，它是该数组中的 first 元素。

Java 有一些处理数组（和集合）的巧妙例程，如果您的第一个数组元素应该像这样被忽略，它们会出现问题或至少需要特殊处理。

您可以使用另一种技术轻松解决此问题：将幻数替换为常量

您可以像这样在 class 中定义常量：

public class towers {
    private static final int STACK_ONE = 0;
    private static final int STACK_TWO = 1;
    private static final int STACK_TREE = 2;

这会像这样更改您的代码：

        integer[STACK_ONE] = new Stack<>();
        integer[STACK_TWO] = new Stack<>();
        integer[STACK_TREE] = new Stack<>();
 //...
                d1 = String.valueOf(integer[STACK_ONE].get(i));

有人可能会建议使用 Java enum 类型，但这在与数组一起使用时有点棘手。

主题评论

既然你选择了我的答案作为解决方案，我觉得我必须为此做出贡献......;o)

在何处添加实际计数

问题是：您在代码中的哪个位置执行可数移动？
很明显是move方法。但并非每次调用 move 方法都是可数移动。如果你在里面输入 if 块，你只能计算移动。所以这是你必须添加 "counting code".

的地方

如何实现计数？

有四种方法可以做到这一点。按复杂程度排序：

算术计算
附加成员变量，
额外参数和return值
传递一个计数器对象。

算术计算

由于底层问题是确定性的，因此可以简单地计算移动次数。此解决方案由 Lew Bloch 提供。

附加成员变量

您可以添加另一个成员变量，例如 N:

 public class towers
 {
    public static int N;
    public static int moveCounter = 0;

在上一节中标识的位置，您只需将这个新成员变量的当前值加一。

额外参数和return值

此解决方案由 Dani 提供

传递一个计数器对象。

这在某种程度上类似于之前的解决方案，只是我们不需要 return 某些东西。但是我们需要一个额外的 class 来做到这一点。因此，这个解决方案对于这个简单的任务来说太复杂了，但我添加它作为记录。

public class towers {
  private static class Counter{
     private int counter = 0;
     void increment(){ counter++;}
     int counted() { return counter; }
  }
  // ...
        Counter numberOfMoves= new Counter(num,);
        StackMove(num,numberOfMoves);
        System.out.println("Number of moves: "+ numberOfMoves.counted());
  // ...
    public static void StackMove(int N, Counter numberOfMoves) {
        for (int d = N; d > 0; d--)
            integer[1].push(d);
        PrintStack();
        move(N, 1, 2, 3, numberOfMoves);
    }
    public static void move(int N, int a, int b, int c, Counter numberOfMoves) {
        if (N > 0) {
            move(N - 1, a, c, b, numberOfMoves);
            int d = integer[a].pop();
            integer[c].push(d);
            PrintStack();
            move(N - 1, b, a, c, numberOfMoves);
            numberOfMoves.count();
        }
     }
  // ...

数河内塔 -Java

Counting towers of hanoi -Java

java

sorting

count

towers-of-hanoi