데이터 구조 및 알고리즘-하노이 타워

Tower of Hanoi는 세 개의 탑 (못)으로 구성된 수학적 퍼즐로, 하나 이상의 고리가 그림과 같습니다.

이 고리는 크기가 다르며 오름차순으로 쌓입니다. 즉, 작은 고리가 큰 고리 위에 놓입니다. 디스크 수가 증가하는 퍼즐의 다른 변형이 있지만 타워 수는 동일하게 유지됩니다.

규칙

임무는 배열 순서를 위반하지 않고 모든 디스크를 다른 타워로 이동하는 것입니다. 하노이 타워에 따라야 할 몇 가지 규칙은 다음과 같습니다.

주어진 시간에 하나의 디스크 만 타워간에 이동할 수 있습니다.
"맨 위"디스크 만 제거 할 수 있습니다.
큰 디스크는 작은 디스크 위에 놓일 수 없습니다.

다음은 세 개의 디스크로 하노이 타워 퍼즐을 푸는 애니메이션 표현입니다.

n 개의 디스크가있는 하노이 타워 퍼즐은 최소한으로 풀 수 있습니다. 2ⁿ−1단계. 이 프레젠테이션은 3 개의 디스크가있는 퍼즐이2³ - 1 = 7 단계.

연산

하노이 타워에 대한 알고리즘을 작성하려면 먼저 적은 양의 디스크 (예 : 1 또는 2)로이 문제를 해결하는 방법을 배워야합니다. 3 개의 타워에 이름을 표시합니다. source, destination 과 aux(디스크 이동을 돕기 위해서만). 디스크가 하나만 있으면 소스에서 대상 페그로 쉽게 이동할 수 있습니다.

2 개의 디스크가있는 경우-

먼저 더 작은 (상단) 디스크를 보조 페그로 이동합니다.
그런 다음 더 큰 (하단) 디스크를 대상 페그로 이동합니다.
마지막으로 작은 디스크를 aux에서 대상 페그로 이동합니다.

이제 우리는 두 개 이상의 디스크로 하노이 타워의 알고리즘을 설계 할 수있는 위치에 있습니다. 디스크 스택을 두 부분으로 나눕니다. 가장 큰 디스크 (n ^번째 디스크)는 한 부분에 있고 다른 모든 (n-1) 디스크는 두 번째 부분에 있습니다.

우리의 궁극적 인 목표는 디스크를 이동하는 것입니다. n소스에서 대상으로 이동 한 다음 다른 모든 (n1) 디스크를 여기에 넣습니다. 주어진 모든 디스크 세트에 대해 동일한 방법을 반복적으로 적용하는 것을 상상할 수 있습니다.

따라야 할 단계는-

Step 1 − Move n-1 disks from source to aux
Step 2 − Move n^th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

하노이 타워의 재귀 알고리즘은 다음과 같이 구동 할 수 있습니다.

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

C 프로그래밍의 구현을 확인하려면 여기를 클릭하십시오 .