Hanoi Tower   하노이 탑

(2018-07-28)
1. 하노이 탑 (Hanoi Tower)재귀(Recursion) 문제의 일종
     - 재귀 호출을 이용해서 풀 수 있는 가장 유명한 예제

  ※ 문제 고안 : 1883년 프랑스 수학자 루카스(Lucas, E.)


2. 문제 기술(記述)

  ㅇ 문제 조건
     - 3개 막대가 고정되어 있고, 중심에 구멍이 뚫려지고 반경이 다른 n개 원반이 있음

  ㅇ 문제 목표
     - 원반을 하나씩 이동시켜 탑 전체를 다른 기둥으로 옮기는 것

  ㅇ 문제 규칙
     - ① 1회에 1개 원반 만 이동
     - ② 작은 원반 위에 큰 원반을 올려놓을 수 없음

  ㅇ (최선의) 이동 횟수 계산
     -  T1 = 1
     -  Tn = 2Tn-1 + 1

     -  Tn = 2n -1


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도
[알고리즘 종류]

 
        최근수정     요약목록(시험중)     참고문헌