015_Hanoi_tower

static void Main(string[] args)
        {
            void Hanoi(int n, char start, char middle, char to)
            {
                if (n == 1)
                {
                    Console.WriteLine("{0} -> {1}",start,to);
                    return ;
                }
                Hanoi(n - 1, start, to, middle); // a -> c 이동 메소드
                Console.WriteLine("{0} -> {1}",start,to); // 가장 큰 원반 이동
                Hanoi(n - 1, middle, start, to); // b -> c 이동 메소드

            }
            Hanoi(4, 'A', 'B', 'C');
        }

가장 어려운 하노이탑 문제.

재귀 : 같은 형태보다 작은 입력을 지닌 자기 자신을 호출 하는 것.

자기자신보다 작은 형태를 찾아야함.

 

1. 재귀 함수를 이용하기 때문에 n == 1인 경우를 처리해줘야한다.

2. 항상 a->c / a ->b / c->b의 형태를 반복한다. //n-1개를 A에서 B로 이동

3. 2번 형태를 반복한 후, 가장 큰 원반을 to로 이동

4. b->a / a->c / a ->c 하면서 하노이 로직 완성. //n-1개를 B에서 C로 이동

 

2,4 번에서 한번에 다 옮길 수 없기때문에 재귀함수와 n-1 을 사용.

 

출력결과

오늘의 반성 : 많은 알고리즘 문제를 풀자