java - 递归断言汉诺塔中的移动次数

Question

我们在大学接到的任务之一是编写一个函数，递归地打印出汉诺塔谜题的 Action :

public static void move(int number, char start, char help, char end) {
    if (number == 1) {
        print("Move the top disk from " + start + " to " + end);
    } else {
        move(number - 1, start, end, help);
        print("Move the top disk from " + start + " to " + end);
        move(number - 1, help, start, end);
    }
}

现在我们必须想出一个函数来计算 n 的移动次数元素并使用断言来检查使用此函数的代码的有效性。

显然该函数由: f(n) = 2*f(n-1) + 1 给出对于 n > 1和f(n) = 1对于 n = 1 。我们可以求解这个递归方程并得到f(n) = 2^n - 1 。

通过添加static int count = 0;到类的顶部并在每个 print 之后递增它语句，我们可以得到总的移动次数:

public static void move(int number, char start, char help, char end) {
    if (number == 1) {
        print("Move the top disk from " + start + " to " + end);
        count++;
    } else {
        move(number - 1, start, end, help);
        print("Move the top disk from " + start + " to " + end);
        count++;
        move(number - 1, help, start, end);
    }
}

然后在检查 counter 值的函数调用后添加断言递归方程的求解形式:

move(n, 'A', 'B', 'C');
assert count == Math.pow(2,n) - 1 : "Number of movements isn't correct.";

这很好用。但是，我很好奇是否有办法使用assert在递归函数本身内部，并使用方程的递归形式检查移动次数 - 类似于 assert count == 2*f(n-1) + 1 。我们可能必须更改 count 的使用，但我不知道如何(或者是否可能)。

注意:print()仅代表标准System.out.println() .

编辑:我更喜欢不需要更改 move 签名的解决方案函数(或者有人说如果没有这样的改变，这肯定是不可能的)

Answer 1

一种方法是将计数作为参数添加到函数中

public static int move(int number, char start, char help, char end, int count)

初始调用类似于

int count == Math.pow(2,n) - 1
move(n,'A','B','C',count);

然后在函数内部

public static int move(int number, char start, char help, char end,int count){
    if(number == 1){
        print("Move the top disk from " + start + " to " + end);
        assert count == 1; 
        return 1;
    }else{
        int subCount1 = move(number-1,start,end,help, (count-1)/2);
        print("Move the top disk from " + start + " to " + end);
        int subCount2 = move(number-1,help,start,end, (count-1)/2);
        assert count == (subCount1 + subCount2 + 1);
        return count; // it's the same as returning 2*f(n-1)+1;
    }
}

count 参数用作预期的断言值。 这是纯粹的直觉，可能需要一些细微的改变。我对 (count-1)/2 部分没有 100% 的认同。

编辑 如果您不想更改方法签名，请尝试以下操作:

public static void move(int number, char start, char help, char end) {
    if (number == 1) {
        print("Move the top disk from " + start + " to " + end);
        count++;
    } else {
        int stepsBeforeMove1 = count;
        move(number - 1, start, end, help);
        int stepsAfterMove1 = count;
        print("Move the top disk from " + start + " to " + end);
        count++;
        int stepsBeforeMove2 = count; //this is just for the sake of clarity
        move(number - 1, help, start, end);
        int stepsAfterMove2 = count;
        assert ((stepsAfterMove1-stepsBeforeMove1) + (stepsAfterMove2-stepsBeforeMove1) + 1) == Math.pow(2,number) - 1;
    }
}