PowerPoint 프레젠테이션

Size: px

Start display at page:

Download "PowerPoint 프레젠테이션"

문영 순
5 years ago
Views:

1 순환알고리즘 C 로쉽게풀어쓴자료구조

2 순환 (recursion) 수행이끝나기전에자기자신을다시호출하여문제해결 - 직접순환, 간접순환 문제정의가순환적으로되어있는경우에적합한방법 ( 예제 ) 팩토리얼 피보나치수열 n! 1 n * ( n 1)! n n 0 fib( n) 1 fib ( n 2) fib( n 1) 1 ` 2 if if n 0 n 1 otherwise 이항계수 하노이의탑

3 팩토리얼의정의 팩토리얼계산 1 n! n*( n 1)! 팩토리얼프로그래밍 : (n-1)! 팩토리얼을계산하기위해함수를다시호출 순환호출 n 1 int factorial(int n) if( n == 1 ) return(1); else return (n * factorial(n-1) ); n 2

4 순환호출과정 팩토리얼함수의호출예제 factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120

5 순환알고리즘구조 순환알고리즘은다음과같은부분들을포함한다. 1. 순환호출을하는부분 2. 순환호출을멈추는부분 int factorial(int n) if( n == 1 ) return(1); else return (n * factorial(n-1) ); 순환을멈추는부분 순환호출을하는부분 만약순환호출을멈추는부분이없다면?. 무한호출

6 순환 vs. 반복 컴퓨터에서의되풀이 순환 (recursion): 순환호출이용 반복 (iteration): for 나 while 을이용한반복 대부분순환 반복가능 순환 순환적인문제에서는자연스러운방법 함수호출의오버헤드 반복 수행속도가빠르다. 순환적인문제에대해서는프로그램작성이아주어려울수도있다. 예 ) 하노이탑

7 팩토리얼의반복적구현 1 n! n*( n 1)*( n 2)* *1 n 1 n 2 int factorial_iter(int n) int k, v=1; for(k=n; k>0; k--) v = v*k; return(v);

8 거듭제곱프로그래밍 숫자 x 의 n 제곱값을구하는문제 : x n 순환적인방법이반복적인방법보다더효율적인예 1) 반복적인방법 double slow_power(double x, int n) int i; double r = 1.0; for(i=0; i<n; i++) r = r * x; return(r);

9 거듭제곱값프로그래밍 2) 순환적인방법 power(x, n) if n=0 then return 1; else if n이짝수 then return power(x 2,n/2); else if n이홀수 then return x*power(x 2, (n-1)/2); double power(double x, int n) if( n==0 ) return 1; else if ( (n%2)==0 ) return power(x*x, n/2); else return x*power(x*x, (n-1)/2);

10 거듭제곱값프로그래밍분석 순환적인방법의시간복잡도 만약 n이 2의제곱이라고가정하면다음과같이문제의크기가줄어든다. n n 반복적인방법과순환적인방법의비교 반복적인방법 순환적인방법 시간복잡도 O(n) O(logn) 실제수행속도 을 수행 7.17 초 0.47 초

11 피보나치수열 개념은순환적이나순환호출을사용하면비효율적인예 피보나치수열 0,1,1,2,3,5,8,13,21, fib( n) fib ( n 순환적인구현 0 1 2) fib( n 1) n 0 n 1 otherwise int fib(int n) if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2));

12 피보나치수열의계산 순환호출을사용했을경우의비효율성 같은항을중복해서계산 n 이커지면더심해짐

13 피보나치수열의반복구현 반복구조를사용한구현 fib_iter(int n) if( n < 2 ) return n; else int i, tmp, current=1, last=0; for(i=2;i<=n;i++) tmp = current; current += last; last = tmp; return current;

14 연습 1 피보나치수열을반복과순환을이용하여구현하고이를비교하여보시오.

15 #include <stdio.h> #include <stdlib.h> int fib_iter(int n); int fib(int n); int main() int n; printf("enter a number : \n"); scanf("%d", &n); printf("fibo(%d)(repetition) is %d\n", n, fib_iter(n) ); printf("fibo(%d)(recursive) is %d\n", n, fib(n)); return 0; int fib_iter(int n) 연습1- 답 if( n < 2 ) return n; else int i, tmp, current=1, last=0; for(i=2;i<=n;i++) tmp = current; current += last; last = tmp; return current; int fib(int n) if( n==0 ) return 0; if( n==1 ) return 1; return (fib(n-1) + fib(n-2));

16 순환, 반복어떤것이더좋은가? 숫자 x 의 n 제곱값을구하는문제 : x n 개념은반복적이나순환이더효율적 피보나치수열 개념은순환적이나반복이더효율적

17 하노이탑문제 문제는막대 A 에쌓여있는원판 n 개를막대 C 로옮기는것이다. 단다음의조건을지켜야한다. 한번에하나의원판만이동할수있다 맨위에있는원판만이동할수있다 크기가작은원판위에큰원판이쌓일수없다. 중간의막대를임시적으로이용할수있으나앞의조 건들을지켜야한다.

18 n=3 일때

19 일반적인경우에는? n-1 개의원판 1 개의원판 C 를임시버퍼로사용하여 A 에쌓여있는 n-1 개의원판을 B 로옮긴다. A 의가장큰원판을 C 로옮긴다. A 를임시버퍼로사용하여 B 에쌓여있는 n-1 개의원판을 C 로옮긴다.

20 문제해결과정 그러면어떻게 n-1 개의원판을 A B 로, 또 B C 로이동하는가? 원래문제가 n 개의원판을 A 에서 C 로옮기는것 따라서지금작성하고있는함수의파라미터를 n-1 로바꾸어순환호출하면된다. // 막대 from 에쌓여있는 n 개의원판을막대 tmp 를사용하여막대 to 로옮긴다. void hanoi_tower(int n, char from, char tmp, char to) if (n==1) from 에서 to 로원판을옮긴다. else hanoi_tower(n-1, from, to, tmp); from 에있는한개의원판을 to 로옮긴다. hanoi_tower(n-1, tmp, from, to);

21 하노이탑최종프로그램 n-1 개의원판을 A 에서 B 로옮기고 n 번째원판을 A 에서 C 로옮긴다음, n-1 개의원판을 B 에서 C 로옮기면된다. #include <stdio.h> void hanoi_tower(int n, char from, char tmp, char to) if( n==1 ) printf(" 원판 1 을 %c 에서 %c 으로옮긴다.\n",from,to); else to); hanoi_tower(n-1, from, to, tmp); printf(" 원판 %d 을 %c 에서 %c 으로옮긴다.\n",n, from, hanoi_tower(n-1, tmp, from, to); main()

22 연습 순환호출에서는순환호출을할때마다문제의크기가작아져야한다. (1) 팩토리얼계산문제에서순환호출이일어날때마다문제가어떻게작아지는가? n! = n * (n-1)! 으로 n 을곱한다음 (n-1)! 을구한다. (2) 하노이의탑에서순환호출이일어날때마다문제의어떻게작아지는가? 하나의원판은이동시킨다음에나머지원판에대하여순환호출을한다.

23 연습 다음함수를 recursive(5) 로호출하였을때화면에출력되는내용과함수반환값을구하라. int recursive(int n) printf( %d\n, n); if(n<1) return 2; else return ( 2*recursive(n-1)+1 );

24 연습 다음함수를 recursive(5) 로호출하였을때화면에출력되는내용과함수반환값을구하라. int recursive(int n) printf( %d\n, n); if(n<1) return 2; else return ( 2*recursive(n-1)+1 ); 함수의반환값 =95

25 연습 연습문제 다음을순환적, 반복적으로계산하는프로그램을작성하여라. 1+1/2+1/3+ + 1/n

26 #include <stdio.h> #include <stdlib.h> double recursive1(int n); int main() int i, n; double sum=0.0; printf("enter number n\n"); scanf("%d", &n); for(i=1;i<=n;i++) sum+=1/(float)i; printf("sum (repetition) is %fl\n", sum); printf("sum (recursive) is %fl\n", recursive1(n)); //system("pause"); system("pause"); return 0; double recursive1(int n) if( n==1 ) return 1.0; else return (1.0/n)+recursive1(n-1);

27 시간복잡도실험 시간복잡도 ] 아래의프로그램 A 는 O(n) 이고프로그램 B 는 O(n 2 ) 이지만 n 이작을때는프로그램 B 가더빠를수도있다. 두개의프로그램을구현하여수행시간을측정하여 n 이어느 정도로커져야프로그램 B 가시간이더걸리는지를실험하라. // 프로그램 A mul = 1; for(i=0;i<n;i++) for(j=1;j<1000;j++) mul = mul *j; // 프로그램 B mul = 1; for(i=0;i<n;i++) for(j=1;j<n;j++) mul = mul *j;

슬라이드 1

슬라이드 1 CHAP 2: 순환 (Recursion) 순환 (recursion) 이란? 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로 되어있는경우에적합한방법 순환 (recursion) 의예 팩토리얼값구하기 피보나치수열 1 n! n*( n 1)! fib( n) 0 1 fib( n 2) n n 0 ` 1 fib( n 1) if n 0 if