자바에서 재귀를 사용하여 하노이 타워의 최소 이동 횟수 계산하기

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)를 이동, 모든 다른 사람을 이동 다시 맨 위 (n - 1).

그래서 ... 당신은 반지의 큰 숫자의 수를 파악해야, 그래서 만약 당신이 빠른 long에 반환 형식을 변경, int의 한계를 오버런 것

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

주 당신을 살 것이다 좀 더 호흡하는 방.