[Java] 재귀 | 하노이 탑

하노이 탑 게임 

https://vidkidz.tistory.com/649

하노이의 탑 (Tower of Hanoi)

---

  2) 하노이 탑
	3개의 기둥이 있고 원반을 옮길 때 작은 원반이 항상 큰 원반 위에 오게 옮기는 방법
	원반은 하나씩만 옮길 수 있다.
	

	원반을 옮길 때 어디서 어디로 옮겼는지 출력하시오.

	원반의 수를 입력받고 모든 원반을 다른 기둥으로 옮길 때 몇번의 이동이 발생하는지 출력 하시오
	
	
	기둥 번호는 1~3번

	원반은 가장 작은 원반이 1 큰 원반일수록 숫자를 1씩 증가

	

-----------------------------------------------------------------------------------------

	이동(원반 번호와 from에서 to로 옮길지를 전달받는다.)

		원반 번호가 1보다 크면 원반 번호 -1을 from에서 from과 to가 아닌 곳으로 이동

		원반 번호를 from에서 to로 옮겼다고 출력

		원반 번호가 1보다 크면 원반 번호 -1을 from과 to가 아닌 곳에서 to로 이동

---

1 . 점화식 이용 

Hanoi(n) = 2 × Hanoi(n-1) + 1 임에 착안하여 나온 점화식은 다음과 같다. 

𝑎𝑛 = 2^n - 1  

public class Hanoi {
    int hanoi1(int n){
        return (int) (Math.pow(2, n)-1);
    }
}

 

public class HanoiMain{
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        System.out.println(hanoi.hanoi1(3));
        System.out.println(hanoi.hanoi1(4));
        System.out.println(hanoi.hanoi1(5));
    }
}

 

실행 결과

 

---

2. 재귀 함수 이용

 

 

    void hanoi2(int n, int from, int mid, int to){
        if(n==1){
            return;
        }
		
        //n-1개를 중간으로 이동
        hanoi2(n-1, from, to, mid);
        
        //가장 아래 원반을 to로 이동
        System.out.println("["+n + "] " + from + " 에서 " + to + "으로 이동");
        
        //n-1개를 중간에서 to로 이동
        hanoi2(n-1, mid, from,to);
    }

 

public class HanoiMain {
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoi2(3, 1, 2, 3);
        System.out.println();
        hanoi.hanoi2(4, 1, 2, 3);
    }
}

실행 결과

---

2-2 재귀 함수 이용

void hanoi3(int num, int from, int to){
        count++;
        //n-1개를 from도 to도 아닌 곳으로 이동!
        if(num>1) {
            hanoi3(num-1, from, 6-from-to);
        }
        System.out.printf("원반 %d를 %d번 기둥에서 %d번 기둥으로 이동했다.", num, from, to);
        // n-1을 from도 to도 아닌 곳에서 to로 이동
        if(num > 1) {
            hanoi3(num - 1, 6 - from - to, to);
        }
    }

---

참고

https://st-lab.tistory.com/96