[ C ] 분할정복 - 하노이탑 (a divide-and-conquer algorithm for the Towers of Hanoi problem)

[ 문제 ]

Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and disks of different sizes. The object is to move the disks that are stacked, in decreasing order of their size, on one of the three pegs to a new peg using the third one as a temporary peg. The problem should be solved according to the following rules: 1 when a disk is moved, it must be placed on one of the three pegs; 2 only one disk may be moved at a time, and it must be the top disk on one of the pegs; and 3 a larger disk may never be placed on top of a smaller disk. (a) Show for your algorithm that . Here denotes the number of steps (moves), given an input of disks.)

 

 

[ 해결 코드 ]

 

#include<stdio.h>
int count = 0;
int hanoi(int disk_num, char from_peg, char to_peg, char tmp_peg) {
	if (disk_num == 1) {
		printf("Move disk#1 from %c to %c \n",from_peg, to_peg);
		count++;
		return;
	}
	hanoi(disk_num - 1, from_peg, tmp_peg, to_peg);//한  번에 한개(1)씩 옮김
	printf("Move disk#%d from %c to %c \n", disk_num,from_peg, to_peg);
	count++;
	hanoi(disk_num - 1, tmp_peg, to_peg, from_peg);

}
int main()
{
	int n = 3;
	int result;
	result = hanoi(n, 'A', 'C', 'B');
	printf("%d", result);
	return 0;
}

 

 

[ 결과 ]

n=3 이므로 2^3 - 1 = 7

총 7번이 실행된다.

 

 

[ 해결 아이디어 ]

 

 

 

[ 참고 사이트 ]

www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

Program for Tower of Hanoi - GeeksforGeeks