[C언어로 쉽게 풀어쓴 자료구조] 02장 순환 - 연습문제

<연습문제>

 

01

5개

 

02

④ 스택

 

03

④ 순환 호출의 순차번호

 

04

③

 

05

n이 줄어들지 않아 무한적으로 반복된다

 

06

기저조건이 없다

 

07 

5

4

3

2

1

0

반환 값 : 16

* 이유 

sum(5) = 5+ sum4  = 16

sum(4) = 4 + sum3  = 11 

sum(3) = 3 + sum 2 = 7 

sum(2) = 2 + sum 1 = 4 

sum(1) = 1 + sum 0 = 2

sum(0) = 1

 

08

출력 :

5

4

3

2

1

0

반환 값 :

95

 

09

출력 : 

10

7

4

1

-2

반환 값:

3

 

10

1

2

3

4

5

 

11

******* 7개

함수가 몇번 실행되는지 알면된다.

 

 

12

evisrucer

* getchar : 사용자가 키보드로 입력한 문자 혹은 

문자열에서 한 글자를 읽어서 반환하는 함수.

* putchar : 문자를 모니터화면(콘솔)에 출력하는 함수.

// 책 오타 putchar(ch) 

 

13.

int sum(int n) {
    if(n==1) return 1;
    else return(n+sum(n-1));
}

14

double div(int n) {
    if(n==1) return 1;
    else return div(n-1)+(double)1/n;
}

15

fib(6) is called
fib(5) is called
fib(4) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(4) is called
fib(3) is called
fib(2) is called
fib(1) is called
fib(0) is called
fib(1) is called
fib(2) is called
fib(1) is called
fib(0) is called

 

16.

int sum(int n) {
    int ans = 0;
    for(int i=0; i<=n; i++) {
        ans+=i;
    }
    return ans;
}

17.

int bc(int n, int k) {
	if (k == 0 || k == n) return 1;
	else return bc(n - 1, k - 1) + bc(n - 1, k);
}

18

(a)

A(3, 2) = 29

A(2, 3) = 9

 

(b)

int ack(int m, int n) {			
	if (m == 0) return (n + 1);
	if (n == 0) return (ack(m - 1, 1));
	return ack(m - 1, ack(m, n - 1));
}

// 책 오타 m-2 -> m-1

 

(c)

int ack2(int m, int n){
	while (m != 0) {
		if (n == 0)	n = 1;
		else n = ack2(m, n - 1);
		m = m - 1;
	}
	return n + 1;
}

 

19 

순환 피보나치 수열은 많은 계산을 반복적으로 수행해서 수행시간이 많이 길어진다.

시간 복잡도 비교하면 반복함수는 O(n), 순환함수는 O(2^n) 이므로 반복이 더 효율적임

 

20

1) n의 값이 작아진다.

2) 하나의 원판을 이동시키고 나머지 원판에 대해서 순환호출이 일어나며 작아진다.

​

21 

flood_fill(x+1, y);
flood_fill(x-1, y);
flood_fill(x, y+1);
flood_fill(x, y-1);

동 서 남 북 으로 움직이면 됨