제귀 호출을 이용한 최대값 구하기

sulbang의 이미지

#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);

까지는 이해가 가는데 저 함수들이 서로 어떻게 동작하는지
자세히 좀 설명해 주세요..

nachnine의 이미지

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]
요렇게 바꿔놓고 보시면 더 편하겠지요

seoleda의 이미지

int Unreal_Tournament(int *,int); 

함수이름 짱입니다. ^^

lifthrasiir의 이미지

하하~ d&c 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!

- 토끼군