하노이탑 공식

하노이탑(Hanoi Tower) 문제는 재귀적 사고를 바탕으로 한 고전적인 퍼즐 문제입니다. 이 문제는 세 개의 기둥과 여러 개의 원반을 사용하며, 각 원반은 크기가 다르고, 원반은 한 번에 하나만 이동할 수 있습니다. 목표는 첫 번째 기둥에 있는 모든 원반을 두 번째 기둥이나 세 번째 기둥으로 옮기는 것입니다. 단, 각 원반은 항상 더 작은 원반 위에 올 수 없으며, 한 번에 한 개의 원반만 옮길 수 있습니다.

하노이탑의 최소 이동 횟수를 구하는 공식은 다음과 같습니다.