ハノイの塔の最小移動回数をJavaの再帰を使用して計算する

Question

ハノイの塔の試合でリングの数に基づいて最小限の移動回数を返すメソッドを開発しています。これまでのところ、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の上にリングのすべてを移動する必要があり、その後、下の1（+ 1）を移動し、その後、他のすべてを移動します上に戻る（n - 1）。あなたは高速intの制限をオーバーランしますので、あなたがlongに戻り値の型を変更し、リングのより大きな数のカウントを把握する必要がある場合を購入すること

そう...

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; 
} 

注意もう少し呼吸室。