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

Question

我们在 Uni 的任务之一是编写一个函数，递归地打印出汉诺塔 谜题的移动：

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 for n > 1 and f(n) = 1 for n = 1。我们可以解这个递归方程得到f(n) = 2^n - 1。

通过将static int count = 0;添加到class的顶部并在每个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-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;
    }
}

Answer 2

如果您将游戏板与解算器分开（因此 Towers 有一个 move 方法，而 Solver 有 solve(towers)），您可以装饰 Towers 到仪器 move。但是你必须摆脱静态方法，你会得到稍微过度设计的 OO 代码而不是过程代码。

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

Recursively assert number of moves in Tower of Hanoi

java

recursion

assert

assertion