증명
-
하노이의 탑Discrete mathmatics and Problem Solving/5 재귀와 귀납 2019. 11. 10. 19:25
하노이의 탑 하노이의 탑 이라는 문제는 일렬로 서있는 세 막대기 중 왼쪽 끝 막대기에 모든 원반들이 크기 순으로 꽂혀있고, 일정한 룰에 따라 그것을 전부 오른 쪽 끝 막대기로 이동하는 것을 묻는 문제이다. 아래는 하노이의 탑 사진 (wikipedia) 큰 원반이 항상 아래에 있어야 한다는 규칙을 준수하면서, 첫 번째 막대기에서 세 번째 막대기로 가는데에 가장 최단 수행 횟수가 존재할 거라 생각하는가? 만약 최단 수행이 존재한다면, 몇 번의 수행 만에 작업을 완료 할 수 있는가? 이에 대해 생각을 해볼 것이다. 하노이의 탑은 브라마의 탑이라고도 불리며 원래는 64개의 원반을 가지고 이동시키는 놀이로 부터 기원한다. 생각 step 1 처음부터 많은 수의 원반을 생각하지 말고 원반의 수를 줄여보자. 원반이 한..