제귀 호출을 이용한 최대값 구하기
글쓴이: 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
f = size/2; l = size - f; tmp[0] = Unreal_Tournament(num, f); tmp[1] = Unreal_Tournament(num+f, l); ret = Unreal_Tournament(tmp, 2);size가 2일때는 결국 case 2 니까
ret = Unreal_Tournament(tmp, 2);
를
ret =( tmp[0] > tmp [1]) ? tmp[0] : tmp[1]
요렇게 바꿔놓고 보시면 더 편하겠지요
여담입니다만..
함수이름 짱입니다. ^^
하하~ d&c 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!
하하~ d&c 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!
- 토끼군
댓글 달기