2007 1학기 10 함수 활용.

Presentation on theme: "2007 1학기 10 함수 활용."— Presentation transcript:

1 2007 1학기 10 함수 활용

2 재귀 함수 Perfect C 재귀 특징 함수는 함수 구현에서 자기 자신의 함수를 호출
구현하려는 알고리즘 자체가 재귀적 특성을 갖는다면, 재귀 함수를 이용하면 쉽게 구현이 가능 재귀 함수는 계속적인 함수의 호출로 인하여 시간과 메모리 공간의 효율성이 떨어지는 단점 일반적으로 재귀 함수는 반복문을 이용한 함수로 변환이 가능 Perfect C

3 재귀 특성 추출 Perfect C n! 계승 수식은 재귀적 특성을 갖음
수식 n!(n factorial)은 1 * 2 * 3 * … * (n-2) * (n-1) * n을 의미 계승 수식은 재귀적 특성을 갖음 즉 n!을 구하기 위해서 (n-1)!을 먼저 구한다면 쉽게 n!을 구할 수 있음 그러나 재귀적 호출이 종료되는 조건이 없다면 무한 호출에 의해 문제가 발생 Perfect C

4 예제 소스 Perfect C binary.c 임의의 십진수를 이진수로 바꾸는 재귀 함수를 작성
임의의 정수를 표준입력으로 입력 받아 그 수의 이진수를 출력 입력한 수가 0이면 종료하며 0보다 크면 이진수 변환을 계속 Perfect C

5 함수의 인자 함수의 인자는 함수를 정의하는 곳에서 기술된 인자인 형식인자(formal parameter)와 함수 호출에서 기술된 실인자(real parameter)로 구분 형식인자에 기술된 변수는 변수의 선언과 같이 식별자의 조건에 맞는 변수 이름을 사용 형식인자의 변수는 그 함수가 호출되는 경우에 메모리에 할당(allocation)되고, 그 함수 실행을 마치면 메모리에서 자동으로 제거 (free, deallocation) Perfect C

6 값의 의한 호출 Perfect C call by value
함수의 형식 인자가 일반 변수형(기본 자료형을 의미)일 때 실제 함수가 호출되는 경우, 실인자의 값을 형식인자에 할당된 새로운 변수에 복사 저장 호출 전에는 변수 number에 10이 저장되었고, 변수 number를 실인자로 함수 increment(number)를 호출 함수 호출 후 변수 number의 값은 변했을까? Perfect C

7 인자와 반환 값 인자 전달 방법이 값에 의한 호출 방법(call by value)에서의 함수 인자는 함수를 호출하는 부분에서 함수를 호출하는 영역으로 자료를 전달하는데 주로 사용 반대로 호출 함수가 작업을 수행한 후, 함수를 호출한 영역으로 결과 값을 전달할 때는 반환 값(return value)을 이용 Perfect C

8 예제 소스 callbyvalue.c 값에 의한 전달 인자를 이해 Perfect C

9 난수 Perfect C Random number
함수 rand()를 이용하면 난수를 발생시킬 수 있는데, 이 함수를 사용하기 위해서는 헤더 파일 stdlib.h 파일을 첨가 함수 rand()에 의해 생성되는 정수는 [0, n] 사이의 임의의 정수 n은 일반적으로 헤더 파일 stdlib.h 파일에 기호 상수 RAND_MAX에 의해 정의, 다음은 Visual C++의 헤더 파일 stdlib.h 파일의 일부로서 기호 상수 RAND_MAX는 16진수로 7fff이고 십진수로 32767 Perfect C

10 시드 이용 Perfect C 매번 난수를 다르게 발생시키기 위하여 시드 (seed) 값을 주는 방법
시드 값이 다르면 함수 rand()에서 발생시키는 난수가 다름 난수 발생 함수 rand()에서 시드 값이 난수의 값을 결정 함수 time()으로 반환되는 값을 함수 srand()의 인자로 이용 함수 time(NULL)은 1970년 1월 1일 이후의 경과된 시간을 초 단위로 반환 함수 이 함수 time()을 이용하려면 헤더 파일 time.h를 첨가   난수에 시드를 주기 위해 함수 srand( time(NULL) )을 호출 Perfect C

11 피보나츠 수 수열 피보나츠 Perfect C 다음 수의 나열인 수열을 살펴보면 앞의 두 수의 합이 그 다음 수
위와 같은 특징의 수열을 피보나츠(Fibonacci) 수열 피보나츠 수는 맨 처음 1202년 수학자 레오나르도 피보나츠 (Leonardo Fibonacci)에 의해 발견 Perfect C

12 피보나츠 수 위 문제에서 매달 토끼장에 있는 토끼의 쌍을 계산해 보면 위 수열로 표현됨을 알 수 있고, 이 수열을 피보나츠(Fibinacci) 수열 n번째 달의 토끼 쌍의 수를 Fn이라 하면, Fn은 다음과 같이 재귀적으로 표현 피보나츠 수를 발생시키는 프로그램을 작성한다면 재귀적 특성을 이용하여 쉽게 구현이 가능 Perfect C

13 피보나츠 구현 Perfect C 여기에서는 재귀적 방법이 아닌 반복적 방법을 이용하여 구현 long fibo(int n) {
int fn, fn1, fn2; int i; if (n <= 1) return n; } else fn2 = 0; fn1 = 1; for (i = 2; i <= n; i++) fn = fn1 + fn2; fn2 = fn1; fn1 = fn; } return fn; Perfect C

14 하노이 탑 Perfect C

15 하노이 문제 해결 문제해결 Perfect C 만일 원반이 1개일 때, 바로 원반을 말뚝 A에서 C로 옮기면 된다
원반이 2개인 경우는 … 원반이 3개인 경우는 … 그렇다면 원반이 64개인 경우는 어떻게 하면 될까? Perfect C

16 분할 정복 방법 Divide and conquer Perfect C

17 하노이 탑 구현 Perfect C 하노이 탑의 분할 정복을 재귀적 함수로 구현
함수 moveHanoi(char, char, char, int)의 인자의 역할은 각각 출발 말뚝, 중간이용 말뚝, 목적 말뚝, 원반의 수 하노이 문제를 해결하려면 함수 moveHanoi(‘A’, ‘B’, ‘C’, 64)로 호출 Perfect C

18 프로그래밍 실습 프로그램 목적 구현 Perfect C
두 개의 양의 정수를 입력 받아, 이 두 수의 최대공약수를 구하는 프로그램을 작성 두 개의 자연수의 공통인 약수를 그들 수의 공약수 그리고 이들 공약수 중에서 가장 큰 수를 최대공약수 구현 두 수의 최대공약수(Greatest Common Devisor)를 구하는 해결 방법 중에서 프로그램에서 쉽게 적용할 수 있는 방법이 유클리드 호제법 함수 호출 큰 수(max) 작은 수(min) gcd(30, 20) 20 30 % 20 == 10 gcd(20, 10) 10 20 % 10 == 0 gcd(10, 0) 그러므로 정답은 10 Perfect C

19 함수 구현 유클리드 호제법의 원리 Perfect C 두 수 a, b가 있을 때, 한 수를 다른 수로 나누었을 때의 식을 고려
예를 들어 a를 b로 나누었더니 몫이 q이고 나머지가 r이었다면 a=bq+r의 식이 성립 이 때, a와 b의 최대공약수는 b와 r의 최대 공약수와 같다(r이 0인 경우에 a와 b의 최대공약수는 b가 된다)라는 것이 유클리드 호제법의 원리 이러한 유클리드 호제법 연산과정은 나머지 연산자 %를 이용하고, 우리가 배운 재귀 함수를 이용하면 쉽게 해결 함수 호출 큰 수(max) 작은 수(min) gcd(30, 20) 20 30 % 20 == 10 gcd(20, 10) 10 20 % 10 == 0 gcd(10, 0) 그러므로 정답은 10 Perfect C

20 함수 구현 이 유클리드의 호제법을 정리 아래에서 A는 B보다 작지 않은 수로 가정 Perfect C

21 이해점검 Perfect C 함수 내부에서 자기 자신의 함수를 호출하는 함수를 (재귀) 함수라 한다.
함수의 인자에서 함수를 정의하는 부분에 기술되는 인자를 (형식) 인자라 한다. 함수의 호출에서 형식인자에 해당하는 변수에 실인자 값을 복사한다는 의미의 원어를 (call by value(값에 의한 호출))라 한다. 인자 전달 방법이 값에 의한 호출 방법(call by value)에서의 함수 (인자)는 함수를 호출하는 부분에서 함수를 호출하는 영역으로 자료를 전달하는데 주로 사용한다. 반대로 호출 함수가 작업을 수행한 후, 함수를 호출한 영역으로 결과 값을 전달할 때는 (반환 값)을 이용한다. 특정한 배열 순서나 규칙을 가지지는 않는 연속적인 임의의 수를 (난수(random number))라 한다. 시스템 라이브러리 함수 ( rand() )를 이용하면 난수를 발생시킬 수 있다. 함수 rand()를 사용하기 위해서는 헤더 파일 ( stdlib.h ) 파일을 첨가해야 한다. 피보나츠의 수에서 F(0)=0, F(1)=1이면 F(4)는 (3)이다. 일반적으로 재귀적으로 해결될 수 있는 문제는 (반복)으로도 해결할 수 있다. Perfect C

22 이해점검 Perfect C 다음 프로그램의 실행 결과는 무엇인가? #include <stdio.h>
void print(int); int main(void) { print(4); return 0; } void print(int n) if (n > 1) print(n-1); printf("Hello C \n"); Perfect C

23 프로그래밍 과제 실습 : - 예제 10.1 ~ 10.7 - 프로그래밍 과제 10장 1, 2, 3, 5, 6, 7, 8
과제물 제출 : 5월 14일까지 2, 5, 7, 8 Perfect C