제귀 호출을 이용한 최대값 구하기
글쓴이: sulbang / 작성시간: 목, 2004/05/27 - 7:25오전
#include "stdio.h" #include "time.h" #include "stdlib.h" #include "conio.h" #define MAX 9 int Unreal_Tournament(int *,int); void main(void) { int Num[MAX],max; srand(time(NULL)); // 초기화 // 할당 for(int i=0; i<MAX; i++) Num[i] = rand(); printf("초기값 : "); for(int j=0; j<MAX; j++) printf("%d ",Num[j]); // 함수 호출 max = Unreal_Tournament(Num,MAX); printf("\n최대값 : %d",max); getch(); } int Unreal_Tournament(int *num, int size) { int f, l; int ret; int tmp[2]; switch(size) { case 1: // 크기 1 ret = *num; break; case 2: // 크기 2 ret = (num[0] > num[1]) ? num[0] : num[1]; break; default: f = size/2; l = size - f; tmp[0] = Unreal_Tournament(num, f); tmp[1] = Unreal_Tournament(num+f, l); ret = Unreal_Tournament(tmp, 2); } return ret; }
제가 이해가 가지 하는 부분이 함수의 제귀 호출 부분이 어떻게 동작하는지
잘 이해가 가지 않습니다..
Unreal_Tournament(num, f); 함수는
두 번째 호출 : Unreal_Tournament(num, 5);
세 번째 호출 : Unreal_Tournament(num, 2);
Unreal_Tournament(num+f, l); 함수는
두 번째 호출 : Unreal_Tournament(num+5, 5);
세 번째 호출 : Unreal_Tournament(num+2, 7);
네 번째 호출 : Unreal_Tournament(num+0, 9);
까지는 이해가 가는데 저 함수들이 서로 어떻게 동작하는지
자세히 좀 설명해 주세요..
Forums:
divide & conquer 네요 ^^ 구간으로 나눠서 (
divide & conquer 네요 ^^
구간으로 나눠서 ( 위에서는 2개 ) 각각 큰걸 구한다음에
( element가 2개 초과면 더 나누고 2개면 비교 1개면 바로 리턴 )
그중에 가장 큰게 전체 중에서도 젤 큰거지요
=DIVIDE
1234567
123 4567
1 23 45 67
=MAX
1 3 5 7
3 7
7
=ANSWER
7
size가 2일때는 결국 case 2 니까
ret = Unreal_Tournament(tmp, 2);
를
ret =( tmp[0] > tmp [1]) ? tmp[0] : tmp[1]
요렇게 바꿔놓고 보시면 더 편하겠지요
여담입니다만..
함수이름 짱입니다. ^^
하하~ d&c 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!
하하~ d&c 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!
- 토끼군
댓글 달기