hoodbilen's warroom

고전적인 하노이타워 문제변형을 풀어봤다.

기존 하노이타워 문제는 3개의 rod와 여러개의 disk가 존재하는데, 1rod에 존재하는 모든 disk를 3rod에 모두 옮기면 되는 문제이다. 단, disk의 크기는 모두 다르고, disk는 한번에 한 개씩 옮길 수 있으며,  큰 disk가 작은 disk 위에 올라가서는 안된다. 라는 조건이 들어가 있다.

위 문제의 코드를 작성하면,

이렇게 작성할 수 있다.

honoi는 재귀함수 방식을 쓰며, 해당 코드를 분석하면

#9 rod1에 있는 n-1개의 disk를 rod2에 옮긴다.

#10 rod1에 있는 마지막 disk를 rod3에 옮긴다.

#11 rod2에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

이렇게 출력이 가능하다.

그럼 이제 하노이타워 변형문제에 대해 설명하겠다.

이번 문제는 disk를 옮길때 rod를 건너 뛸 수 없다는 조건이 들어간다. 말 그대로 rod1에서 rod3으로 옮기고 싶다면 반드시 "rod1에서 rod2", "rod2에서 rod3"이렇게 두번 출력해주어야 한다는 말이다.

해당 문제를 코드로 작성하면

이런식으로 작성할 수 있다.

해당코드를 분석하면

#10 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

#11 rod1에 있는 마지막 disk를 rod2에 옮긴다.

#12 rod3에 있는 n-1개의 disk를 rod1에 옮긴다.

#13 rod2에 있는 마지막 disk를 rod3에 옮긴다.

#14 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

출력 마지막 부분을 보면 이동한 횟수가 나오는데, 해당 코드는 𝑇𝑛 = 3𝑇(𝑛−1) + 2 그리고 𝑇1 = 2. 를 따른다.

해당 수열을 정리하면,  이동한 최소 횟수는 𝑇𝑛 = 3^𝑛 − 1 를 따르는 것을 알 수 있다.