[C로 쓴 자료구조론] 1장 연습문제-11번(하노이의 탑) 풀이

 

 

 

 

 

 

 

 

11번 문제

---

 

세 탑이 있는데, 첫 번째 탑에는 반경이 서로 다른 64개의 원 판들이 쌓여 있다. 이때 각 원판은 반경이 큰 순서로 아래부터 쌓여있다. 이제, 다음 규칙에 따라 수도승들이 첫 번째 탑에서 세 번째 탑으로 원판을 옮기려 한다.

 

(a) 한 번에 1개의 원판만을 다른 탑으로 옮길 수 있다.

(b) 쌓아놓은 원판은 항상 위의 것이 아래 것보다 작아야 한다.

 

이 작업을 수행하는데 필요한 이동 순서를 출력하는 순환 함수를 만들어라.

 

---

 

 

그냥 재귀함수로 구현할게요~

https://dokhakdubini.tistory.com/190?category=814319

[재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들

 

 

 

#include <stdio.h>
#include <stdlib.h>

void move(int from, int to);
void hanoi(int n, int from, int to, int via);

int count=0;

int main() {
	int n;
	printf("Please input the number of disks: ");
	scanf("%d", &n);
	if (n < 1) {
		fprintf(stderr, "Please input number bigger than 0.\n");
		exit(EXIT_FAILURE);
	}

	hanoi(n, 1, 3, 2);

	printf("Thus, the mininal number of moves is %d.", count);
	return 0;
}

void hanoi(int n, int from, int to, int via) {
	if (n == 1) {
		move(from, to);
		count++;
	}
	else {
		hanoi(n - 1, from, via, to);
		move(from, to);
		count++;
		hanoi(n - 1, via, to, from);
	}
}

void move(int from, int to) {
	printf("The upmost disk in rod %d is moved to rod %d.\n", from, to);
}

 

 

 

 

굳굳