Microsoft PowerPoint - chap-09.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - chap-09.pptx"

성민 강
5 years ago
Views:

1 쉽게풀어쓴 C 언어 Express 제 9 장함수와변수

2 이번장에서학습할내용 반복의개념이해 변수의속성 전역, 지역변수 자동변수와정적변수 재귀호출 이번장에서는함수와변수와의관계를집중적으로살펴볼것이다. 또한함수가자기자신을호출하는재귀호출에대하여살펴본다

3 변수의속성 변수의속성 : 이름, 타입, 크기, 값 + 범위, 생존시간, 연결 범위 (scope) : 변수가사용가능한범위, 가시성생존시간 (lifetime): 메모리에존재하는시간연결 (linkage): 다른영역에있는변수와의연결상태

4 범위 범위 (scope): 변수가접근되고사용되는범위 범위는선언되는위치에따라서결정된다. 범위의종류 파일범위 (file scope): 함수의외부에서선언, 전역 (global) 변수 함수범위 (function scope): 레이블의범위 블록범위 (block scope): 블록안에서선언, 지역 (local) 변수 함수원형범위 : 함수의원형에등장하는매개변수에적용

5 지역변수 Q) 지역변수란? A) 블록안에서선언되는변수 Q) 블록이란? A) 중괄호로둘러싸인영역

6 지역변수 지역변수의선언 : 블록의맨첫부분에서선언 int sub1(void) int x; // 함수의시작부분에선언 int y; // 오류가아님... 지역변수의범위 : 선언된블록안에서만접근과사용이가능 void sub1(void) int x; // 지역변수 x 선언 x = 0; // OK int y; // 지역변수 y 선언 x = 1; // OK y = 2; // OK x = 3; // OK y = 4; // 1 컴파일오류!! 컴퓨터프로그래밍 기초

7 같은이름의지역변수

8 지역변수의생존기간

9 지역변수예제 #include <stdio.h> int main(void) id) int i; 블록이시작할때마다생성되어초기화된다. for(i = 0;i < 5; i++) int temp = 1; printf("temp = %d\n", temp); temp++; return 0; temp = 1 temp = 1 temp = 1 temp = 1 temp = 1

10 함수의매개변수 #include <stdio.h> int inc(int counter); int main(void) int i; i=10; printf(" 함수호출전 i=%d\n", i); inc(i); printf(" 함수호출후 i=%d\n", i); return 0; int inc(int counter) counter++; return counter; 값에의한호출 (call by value) 매개변수도일종의지역변수임 함수호출전 i=10 함수호출후 i=10

11 전역변수 #include <stdio.h> int x = 123; void sub1() printf("in sub1() x=%d\n",x); void sub2() printf("in sub2() x=%d\n",x); int main(void) sub1(); sub2(); 전역변수 : 함수의외부에선언되는변수 // 전역변수 x 접근 // 전역변수 x 접근 return 0; In sub1() x=123 컴퓨터프로그래밍 In sub2() 기초 x=123

12 전역변수의초기값과생존기간 #include <stdio.h> int counter; // 전역변수 void set_counter(int i) counter = i; // 직접사용가능 int main(void) printf("counter=%d\n", counter); counter = 100; // 직접사용가능 printf("counter=%d\n", counter); * 전역변수의초기값은 0 counter=0 counter=100 counter=20 * 생존기간은프로그램시작부터종료 set_counter(20); printf("counter=%d\n", counter); return 0;

13 전역변수의사용 // 전역변수를사용하여프로그램이복잡해지는경우 #include <stdio.h> void f(void); int i; int main(void) for(i = 0;i < 5; i++) f(); return 0; void f(void) for(i = 0;i < 10; i++) printf("#"); 출력은어떻게될까요? ##########

14 같은이름의전역변수와지역변수 // 동일한이름의전역변수와지역변수 #include <stdio.h> int sum = 1; // 전역변수 int main(void) int i = 0; int sum = 0; // 지역변수 지역변수가전역변수를가린다. for(i = 0; i <= 10; i++) sum += i; printf("sum = %d\n", sum); return 0; 컴퓨터프로그래밍 sum 기초 = 55

15 생존기간 정적할당 (static allocation): 프로그램실행시간동안계속유지 자동할당 (automatic allocation): 블록에들어갈때생성 블록에서나올때소멸 생존기간을결정하는요인 변수가선언된위치 저장유형지정자 저장유형지정자 auto register it static extern 변수생성 변수소멸

16 저장유형지정자 auto 변수를선언한위치에서자동으로만들어지고블록을벗어나게되며자동으로소멸되는저장유형을지정 지역변수는 auto가생략되어도자동변수가된다. int main(void) auto int sum = 0; int i = 0; 전부자동변수로서함수가시작되면생성되고끝나면소멸된다.

17 저장유형지정자 static #include <stdio.h> void sub(void); int main(void) int i; for(i = 0;i < 3; i++) sub(); return 0; 자동지역변수 void sub(void) int auto_count = 0; static int static_count = 0; auto_count=1 static_count=1 auto_count=1 static_count=2 auto_count=1 static_count=3 정적지역변수로서 static을붙이면지역변수가정적변수로된다. auto_count++; static_count++; printf("auto_count=%d\n", auto_count); printf("static_count=%d\n", static_count);

18 저장유형지정자 register 레지스터 (register) 에변수를저장. register int i; for(i = 0;i < 100; i++) sum += i; CPU안의레지스터에변수가저장됨

19 저장유형지정자 extern extern1.c #include <stdio.h> 컴파일러에게변수가다른곳에서선언되었음을알린다 int x; // 전역변수 extern int y; // 현재소스파일의뒷부분에선언된변수 extern int z; // 다른소스파일의변수 int main(void) extern int x; // 전역변수 x를참조한다. 없어도된다. x = 10; y = 20; z = 30; return 0; int y; // 전역변수 extern2.c int z;

20 연결 연결 (linkage): 다른범위에속하는변수들을서로연결하는것 외부연결 내부연결 무연결 전역변수만이연결을가질수있다. static 지정자를사용한다. static이없으면외부연결 static이있으면내부연결 범위 범위

21 연결예제 #include <stdio.h> int all files; // 다른소스파일에서도사용할수있는전역변수 static int this_file; // 현재의소스파일에서만사용할수있는전역변수 extern void sub(); linkage1.c int all_files; // 다른소스파일에서도사용할수있는전역변수 int main(void) 연결 sub(); printf("%d\n", all_files); return 0; linkage2.c extern int all_files; void sub(void) all_files = 10; 10

22 다중소스파일 연결은흔히다중소스파일에서변수들을연결하는데사용된다.

23 함수앞의 static main.c #include <stdio.h> extern void f2(); int main(void) f2(); return 0; static이붙는함수는파일안에서만사용할수있다 sub.c static void f1() printf("f1() f1() 이호출되었습니다.\n"); void f2() f1(); printf("f2() 가호출되었습니다.\n");

24 저장유형정리 일반적으로는자동저장유형사용권장 자주사용되는변수는레지스터유형 변수의값이함수호출이끝나도그값을유지하여야할필요가있다면지역정적 만약많은함수에서공유되어야하는변수라면외부참조변수 저장유형키워드정의되는위치범위생존시간 자동 auto 함수내부지역임시 레지스터 register 함수내부지역임시 정적지역 static 함수내부지역영구 전역없음함수외부모든소스파일영구 정적전역 static 함수외부하나의소스파일영구 외부참조 extern 함수외부모든소스파일영구

25 main.c #include <stdio.h> unsigned random_i(void); double random_f(void); extern unsigned call_count; 예제 // 외부참조변수 int main(void) register int i; // 레지스터변수 for(i = 0; i < 10; i++) printf("%d ", random_i()); printf("\n"); for(i = 0; i < 10; i++) printf("%f ", random_f()); printf("\n 함수가호출된횟수 = %d \n", call_count); count); return 0;

26 예제 random.c // 난수발생함수 #define SEED #define MULT #define INC 함수가호출된횟수 = 20 #define MOD unsigned int call_count = 0; static unsigned seed = SEED; // 전역변수 // 정적전역변수 unsigned random_i(void) seed = (MULT*seed + INC) %MOD; call_count++; return seed; double random_f(void) seed = (MULT*seed + INC) % MOD; call_count++; return seed / (double) MOD;

27 순환 (recursion) 이란? 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 팩토리얼의정의 n! 1 n * ( n 1)! n n 1 2 팩토리얼프로그래밍 #1: (n-1)! 팩토리얼을구하는서브함수를따로제작 int factorial(int n) if( n==1)return(1); else return (n * factorial_n_1(n-1) );

28 팩토리얼구하기 #1 팩토리얼프로그래밍 #2: (n-1)! 팩토리얼을현재작성중인함수를다시호출하여계산 ( 순환호출 ) int factorial(int n) if( n>=1)return(1); else return (n * factorial(n-1) ); 3! 은? 3! 를 2! 를 1! 은계산하려면계산하려 1 3! = 3*2! 면 2! = 2*1! 3! 는? 2! 는? 1! 는? 6 2 1

29 팩토리얼구하기 #2 팩토리얼의호출순서 factorial(3) = 3 * factorial(2) = 3 * 2 * factorial(1) = 3 * 2 * 1 4 = 3 * 2 = 6 3 factorial(3) if( 3 >= 1 ) return 1; else return (3 * factorial(3-1) ); factorial(2) if( 2 >= 1 ) return 1; else return (2 * factorial(2-1) ); factorial(1) if( 1 >= 1 ) return 1;

30 순환알고리즘의구조 순환알고리즘은다음과같은부분들을포함한다. 순환호출을하는부분 순환호출을멈추는부분 int factorial(int n) if( n == 1 ) return 1 순환을멈추는부분 else return n * factorial(n-1); 순환호출을하는부분 만약순환호출을멈추는부분이없다면?. 시스템오류가발생할때까지무한정호출하게된다.

31 순환 <-> 반복 컴퓨터에서의되풀이 순환 (recursion): 순환호출이용 반복 (iteration): for나 while을이용한반복 대부분의순환은반복으로바꾸어작성할수있다. 순환 1!=1 3! 를 2!=2 계산하려면 순환적인문제에서는자 3!=6 3! = 3*2! 연스러운방법 2! = 2 1! 함수호출의오버헤드 반복 수행속도가빠르다. 순환적인문제에대해서는프로그램작성이아주어려울수도았다. 2! 를계산하려면 2! = 2*1! 2! 는? 1! 는? 2 1 1! 은 1

32 팩토리얼의반복적구현 n! n * ( n 1 1) * ( n 2) * *1 n n 1 2 int factorial_iter(int n) int k, value=1; for(k=1; k<=n; k++) value = value*k; return(value);

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

34 거듭제곱값구하기 #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);

35 거듭제곱값구하기 #3 순환적인방법의시간복잡도 만약 n 이 2 의제곱이라고가정하면다음과같이문제의크기가줄어든다. n n 반복적인방법과순환적인방법의비교 반복적인함수 slow_power 순환적인함수 power 시간복잡도 O(n) O(logn) 실제수행속도 7.17 초 0.47 초

36 피보나치수열의계산 #1 순환호출을사용하면비효율적인예 피보나치수열 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));

37 피보나치수열의계산 #2 순환호출을사용했을경우의비효율성 같은항이중복해서계산됨 예를들어 fib(6) 을호출하게되면 fib(3) 이 4 번이나중복되어서계산됨 이러한현상은 n 이커지면더심해짐 fib(6) fib(4) fib(5) fib(2) fib(3) fib(3) fib(4) fib(2) fib(3) fib(1) fib(2) fib(1) fib(2) fib(2) fib(3)

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

39 3 개의원판인경우의해답 A B C A B C A B C A B C A B C A B C A B C A B C

40 n 개의원판인경우 n-1개의원판을 A에서 B로옮기고 n 번째원판을 A 에서 C 로옮긴다음, n-1개의원판을 B에서 C로옮기면된다. n-1 개의원판 1 개의원판 A 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 hanoi_tower(n-1, from, to, tmp); printf(" 원판 %d을 %c에서 %c으로옮긴다.\n",n, from, to); hanoi_tower(n-1, tmp, from, to); main() hanoi_tower(4, 'A', 'B', 'C'); A B C A B C A B C

41 Q & A

슬라이드 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