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

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 알고리즘인 건 맞고요. 이름이 정말 인상적입니다!

- 토끼군

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.