22034,

1/1102

용용

하노이탑 알고리즘.. 질문좀.

http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Board&no=30520 [복사]

#include<stdio.h>

void hanoi(int, char, char, char);

int main()
{
        int n;
        printf("원반의 갯수:");
        scanf("%d",&n);

        hanoi(n,'a','b','c');

        return 0;
}
void hanoi(int n, char a, char b, char c)
{
        if(n>0)
        {
                hanoi(n-1,a,c,b);
                printf("%d번 원반을 %c에서 %c 로 옮김\n",n,a,b);
                hanoi(n-1,c,b,a);
        }
}

이게 어떻게 돌아가는지 이해가안갑니다... 그말은 즉, 제가 재귀함수를 재대로 이해못했단소리인데. 재귀함수를 보고 봐도 잘모르겠네요...
코드 설명좀해주시면 감사하겠습니다.

Hit : 6513 Date : 2013/04/06 09:46


dwdwzzz	그림그려가면서 보면 이해하기가 쉽습니다. 전 책보고 알았는데 한번 스포일당하면 재미가없기때문에 약간만 힌트를드릴께요 ㄷㄷ.. 위의 소스는 하노이의 탑의 원반을 옴겼다고 출력하는함수라고 볼수있습니다. 한쪽에 n개의 원반이 있을때 그것을 다른곳으로 옮기는게 목적이죠. 제한은 큰원반이 작은원반위로갈수 없다는것이구요. 그런데 3개짜리 원반을 일단 생각해봅시다. a b c 고리가 있고 a에 1 2 3 크기의 원반이 순서대로있습니다. 처음에는 1크기의 원반을 b에 옴기고 c에 2크기의 원반을 옴깁니다. 1크기를 c에 옴기고 a에 남아있는 3크기의 원반을 b에 옴깁니다. 여기까지했다면 3크기의 원반을 옴기기전의 일과 비슷한 일을하면 결국에는 2 1 크기의 원반이 b로 가게되겠죠. 여기서 더말하면 재미가없어지겠지만 쪼끔만 더 말하면 3크기의 원반을 옴기는건 가장 중간이고 그걸 기준으로 처음일과 나중일은 비슷하다고 볼수있습니다. 위의 소스코드에서 n번째를 옴기는 과정을 출력하는게 바로 3크기의 원반을 옴기는거라고 보시면됩니다. n-1과 a b c 가 바뀌어있는건 n번째 원반을 옴기기전에는 특정한 규칙에따라 고리를 바꾸어 보는 것이구요. 재귀함수라고해서 굳이 어려워할필요가없는게 그냥 내용만같은 다른함수를 호출했다고 봐도 무방합니다. 어설프게 설명하긴했는데 이런 알고리즘같은건 혼자서해보는게 머리에좋습니다. 남이 풀어주면 재밌는 부분이 없기때문이죠 -_-ㅋㅋ	2013/04/07