하노이 타워에 간단한 코드는 https://gunhoflash.tistory.com/41 참고.
일반적인 하노이 타워 문제에서, 한 기둥에 있는 n개의 원판을 다른 기둥으로 완전히 이동시키는 데 필요한 원판 이동 횟수를 F(n) 이라 할 때, F(n)을 n에 대한 식으로 나타내보자.
- 먼저, F(0) = 0, F(1) = 1 이다.
- 자연수 n에 대해, F(n) = F(n - 1) + 1 + F(n - 1) = 2F(n - 1) + 1 이다.
따라서,
F(n) = 2F(n - 1) + 1
= 2(2F(n - 2) + 1) + 1 = 4F(n - 2) + 3
= 4(2F(n - 3) + 1) + 3 = 8F(n - 3) + 7
= ...
= 2^((n - 1) - 1)(2F(n - (n - 1)) + 1) + (2^((n - 1) - 1) - 1) = 2^(n - 1)F(n - (n - 1)) + (2^(n - 1) - 1)
= 2^(n - 1)(F(1) + 1) - 1
= 2^n - 1
즉, F(n) = 2^n - 1 이다. 그리고 이것은 n = 0 일때도 성립한다.