在 java 中使用递归计算汉诺塔中的最小移动次数

Question

我一直在研究一种方法，returns汉诺塔游戏中可以走的最少步数得意地基于环数。到目前为止，我已经有了可以计算 2^n（n 是环数）的基本代码。但是，当我减去 1 时，该方法的行为就好像它们没有环一样。

    static int countHanoiMoves(int n)
{   
    int unSubtrctAnswer = 0;        

    if(n == 0) 
    {
        return  1;
    }

    int halfPower = countHanoiMoves(n / 2);

    if (n % 2 == 1)
    {
        unSubtrctAnswer = (2 * halfPower * halfPower);
    }
    else
    {
        unSubtrctAnswer = (halfPower * halfPower);
    }

    return unSubtrctAnswer - 1;
}

Answer 1

正如 Andreas 在评论中所建议的，您的算法不正确。递归的解法其实要简单很多。

考虑：要移动 n 个环，您首先需要移动底部 (n - 1) 顶部的所有环，然后移动底部 (+ 1)，然后移动所有其他人重回榜首（又是 n - 1）。

所以...

static int countHanoiMoves(int n) {

    if (n == 0) return 0;

    if (n < 0) throw new RuntimeException("What? A negative number of rings?");

    // count(n-1) + 1 + count(n-1)... since we aren't actually moving
    // the rings, but merely counting the number of moves, we can do
    // it a little more cheaply by just multiplying by 2 rather than
    // calling the recursive method twice

    return 2 * countHanoiMoves(n - 1) + 1;
}

请注意，您将很快超出 int 的限制，因此如果您需要计算更多响铃次数，将 return 类型更改为 long 将给你多一点喘息的空间。

在 java 中使用递归计算汉诺塔中的最小移动次数

Counting the minimum number of moves in Tower of Hanoi using recursion in java

java

recursion

counting

towers-of-hanoi