하노이의 탑 (Tower of Hanoi)

조건을 만족시키면서 모든 원판을 그 순서 그대로 다른 기둥으로 옮기는 게임

문제

https://www.acmicpc.net/problem/1914

---

옮긴 횟수 구하기

1(1) - 1개
1 3

2(1 + 2) - 3개
1 3
1 2
3 2

3 (1 + 2 + 4) - 7개
1 3
1 2
3 2
1 3
2 1
2 3
1 3

4 (1 + 2 + 4 + 8) - 15개
1 3
1 2
3 2
1 3
2 1
2 3
1 3
1 2
3 2
3 1
2 1
3 2
1 3
1 2
3 2

1 3 7 15... 순서로 증가하는 것을 볼 수 있다
따라서 옮긴 횟수는 (2^n - 1) 으로 계산할 수 있다

이 문제는 알고리즘보다는 2^100정도 되는 큰 수를 어떻게 표현할지가 더 어려운 것 같다...
개인적으로는 long double과 char형 배열을 써서 해결했다

---

알고리즘 (재귀)

void hanoi(int n, int start, int mid, int end)
{
    if (n == 1)
        printf("%d %d\n", start, end);
    else
    {
        hanoi(n - 1, start, end, mid);
        printf("%d %d\n", start, end);
        hanoi(n - 1, mid, start, end);
    }
}

n개의 원반을 옮기기 위해서는 위에 존재하는 n-1개의 원반을 옮겨야한다
따라서 재귀를 사용한다

또한 동일한 순서를 지키면서 이동시켜야하기 때문에
start(이동시킬 원판이 있는 기둥), middle(임시로 놔둘 기둥), end(이동시킨 원판을 위치시킬 기둥)으로 재귀를 불러서 알고리즘을 짰다