【코딩】 C 언어로 하노이 탑 (Hanoi Tower)

C 언어로 하노이 탑 (Hanoi Tower)

 

추천글 : 【C 언어】 C 언어 목차

---

1. 개요 [본문]

2. 최소 이동 횟수 [본문]

3. C 코드 [본문]

---

 

1. 개요 [목차]

⑴ 정의

하노이의 탑(Hanoi Tower)은 프랑스의 수학자 뤼카가 1883년 다음과 같은 이야기로 처음 소개한 것으로, n개의 원판을 옮기기 위해 필요한 최소 이동횟수를 구하는 문제이다. 

⑵ 설화

인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고, 그 안에 3개의 다이아몬드 바늘이 동판 위에 새겨져 있다. 바늘의 높이는 1 큐빗이고, 굵기는 별의 몸통만 하다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있다. 이것은 신성한 브라흐마의 탑이다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮겼으며, 이 일이 끝날 때 탑은 무너지고 세상은 종말을 맞이하게 된다고 알려져 있다.

 

 

2. 최소 이동 횟수 [목차]

⑴ 개괄 

예를 들어 원판이 두 개라고 하고, A 기둥에서 C 기둥으로 모두 옮기려고 한다면, A → B, A → C, B → C로 옮기면 된다. 이 문제를 해결하기 위해 수학자들은 다양한 시도를 하였으며, 그 결과 최소 이동횟수가 2n-1임을 알아냈다.

⑵ 점화 관계

① 점화식 : a_n+1 = 2a_n + 1 

② 점화식의 이해를 돕는 도식

 

 

 

3. C 코드 [목차]

 

#include <stdio.h>
#include <stdlib.h>
/* This is an algorithm to solve the Hanoi Tower problem */
// Step 1. transfer (n-1)-th floor pyramid to other blank(A or B)
// Step 2. transfer the largest disk to C
// Step 3. repeat step 1 and step 2 (n is getting smaller)

void Hanoi(int n, char A, char B, char C){
	if(n == 1) printf("%c → %c\n", A, C);
	else{
		Hanoi(n-1, A, C, B);
		printf("%c → %c\n", A, C);
		Hanoi(n-1, B, A, C);
	}
}

int main(int argc, char *argv[]) {
	int n;
	scanf("%d", &n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

 

입력: 2016.02.08 19:39

수정: 2022.09.08 13:24