2

我的任务是添加一堆打印语句来显示河内塔的完整输出，以查看和了解它在幕后所做的事情，而不仅仅是给你最终结果。

class TowersApp {
    static int nDisks = 3;
    public static void main(String[] args) {


        doTowers(nDisks, 'A', 'B', 'C');
    }

    public static void doTowers(int topN, char from, char inter, char to) {
        int i = 0;

        if(topN==1) {
            System.out.println("Enter (" + topN + " disk): " + "s=" + from + ", i=" + inter + ", d=" + to);
            System.out.println("Base case: move disk " + topN + " from " + from + " to "+ to);
            System.out.println("Return (" + topN + " disk)"); }
        else {
            System.out.println("Enter (" + topN + " disks): " + "s=" + from + ", i=" + inter + ", d=" + to);
            doTowers(topN-1, from, to, inter);
            System.out.println("Move bottom disk " + topN +
                    " from " + from + " to "+ to);
            doTowers(topN-1, inter, from, to);
            System.out.println("Return (" + topN + " disks)");

        }
    }
}

这是我的输出。我唯一缺少的是indentation。我需要有一个用于第一级递归的选项卡，2 个用于第二级递归的选项卡等等......这就是我的意思：

电流输出：

Enter (3 disks): s=A, i=B, d=C
Enter (2 disks): s=A, i=C, d=B
Enter (1 disk): s=A, i=B, d=C
Base case: move disk 1 from A to C
Return (1 disk)
Move bottom disk 2 from A to B
Enter (1 disk): s=C, i=A, d=B
Base case: move disk 1 from C to B
Return (1 disk)
Return (2 disks)
Move bottom disk 3 from A to C
Enter (2 disks): s=B, i=A, d=C
Enter (1 disk): s=B, i=C, d=A
Base case: move disk 1 from B to A
Return (1 disk)
Move bottom disk 2 from B to C
Enter (1 disk): s=A, i=B, d=C
Base case: move disk 1 from A to C
Return (1 disk)
Return (2 disks)
Return (3 disks)

期望的输出：

Enter (3 disks): s=A, i=B, d=C
    Enter (2 disks): s=A, i=C, d=B
        Enter (1 disk): s=A, i=B, d=C
            Base case: move disk 1 from A to C
        Return (1 disk)
    Move bottom disk 2 from A to B
Enter (1 disk): s=C, i=A, d=B
...................................

我需要某种计数器来“计算”我进入该功能的次数吗？但是，这甚至可以通过递归实现吗？也许我在分析什么时候有一个更简单的解决方案来解决这个问题？

4

4 回答 4

2

一种简单的方法是添加一个名为indentdoTowers 的 String 参数，该参数将被添加到所有输出中。来自 main 的调用将传递一个空字符串，doTowers 中的每个调用都会向该参数添加空格或制表符（即doTowers(indent+" ",...)）。您将每个更改System.out.println(...)为System.out.println(indent+...)

于 2010-11-22T16:12:20.167 回答
2

最简单但可能不太优雅的方法是将递归深度作为一个完整参数传递给您的函数，并随着每个新的深度级别增加它：

public static void doTowers(int topN, char from, char inter, char to, int depth)

....

doTowers(..., depth + 1)
doTowers(..., depth + 1)

从0你的主要功能开始。然后，只需\t为每个depth.

于 2010-11-22T16:12:35.610 回答
1

当然，计数器很好地解决了这个问题。你如何在递归中得到它？很简单，将其作为参数传递！

于 2010-11-22T16:10:35.643 回答
1

为什么不传入一个额外的参数，每次递归调用都会增加这个参数？

public static void doTowers(int topN, char from, char inter, char to, int depth)

后来

doTowers(topN-1, from, to, inter, depth+1);

深度将向您显示要使用的选项卡数量。第一次调用的深度为 0。

于 2010-11-22T16:26:04.857 回答