하노이의 탑


원반이 n개인 하노이 탑이 어떻게 이동되는지 몇번 이동하는지 구해보자.



조건


하노이의 탑은 다음과 같이 크기 가 다른 원반이 한 기둥에 놓여져 있고 


원반을 모두 왼쪽에서 오른쪽으로 옮겨야 한다.


원반은 큰 것이 아래로 가게 쌓아야 하며 작은 원반 위에 큰 원반이 올 수 없다.


원반을 옮길 때에는 가장 위에 쌓여있는 원반 부터 옮겨야 한다.




1. 원반이 1개 일때


1번에서 3번으로 옮기면 된다.



2. 원반이 2개 일때


1번 기둥의 맨 위에 있는 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )


1번 기둥의 마지막 남아있는 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )


2번 기둥에 있는 원반 하나를 3번 기둥에 옮긴다. ( 2 -> 3 )



3. 원반이 3개 일때


1. 1번 기둥의 가장 작은 원반 하나를 3번 기둥에 옮긴다. ( 1 -> 3 )


2. 1번 기둥의 중간 원반 하나를 2번 기둥에 옮긴다. ( 1 -> 2 )


3. 3번 기둥의 가장 작은 원반 하나를 2번 기둥에 옮긴다 ( 3 -> 2 )


4. 1번 기둥의 가장 큰 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )


5. 2번 기둥에 가장 작은 원반 하나를 1번 기둥에 옮긴다. ( 2 -> 1 )


6. 2번 기둥에 중간 원반 하나를 3번 기둥에 옮긴다. ( 2 > 3 )


7. 1번 기둥에 가장 작은 원반을 3번 기둥에 옮긴다. ( 1 -> 3 )


총 7번 옮김



4. 원반이 n개 일때


1번 기둥에 있는 n-1개 원반을 2번 기둥에 옮긴다.


1번 기둥에 가장 큰 원반을 3번 기둥으로 옮긴다.


2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.



소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package test1;
 
public class Hanoi {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("n=3");
        MyHanoi myHanoi = new MyHanoi();
        
//        myHanoi.hanoiFunction(3, 1, 2, 3);
        System.out.println("총 옮긴 횟수: "+myHanoi.hanoiFunction(3123)); // 2의 n제곱 - 1 = 옮긴 횟수
    }
}
class MyHanoi{
    int count = 0 ;
    int hanoiFunction(int n, int first, int second, int third) { 
        if(n==1){
            System.out.println(first+"->"+third); 
            count++;
            return count;
        }
        hanoiFunction(n-1, first, third, second);  
        System.out.println(first+"->"+third); 
        count++
        hanoiFunction(n-1, second, first, third); 
        
        return count;
    }    
}
cs



출력결과


마지막으로 해당 소스를 첨부한다.


Hanoi.java





+ Recent posts