C언어로 쉽게 풀어쓴 자료구조 [개정3판] - Ch 2 연습 문제
1) 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개변수로 5를 주었다면 최대 몇 개의 factorial 함수의 활성 레코드가 동시에 존재할 수 있는가?
답: 5개
2) 순환 호출을 하였을 경우에 활성 레코드들이 저장되는 위치는 어디인가?
(1) 순환호출 함수 내부
(2) 변수
(3) 배열
(4) 스택
답: 4번 (스택)
3) 다음 중 활성 레코드에 저장되지 않는 것은 무엇인가?
(1) 매개변수의 값
(2) 함수 호출이 끝나고 복귀할 주소
(3) 지역 변수
(4) 순환 호출의 순차번호
답: 4번 (순환 호출의 순차번호)
4) 하나의 함수가 호출할 수 있는 순환 호출의 개수는?
(1) 1번
(2) 2번
(3) 스택이 허용하는 한도
(4) 무제한
답: 4번 (스택이 허용하는 한도)
5) 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n) {
if (n == 1) return 0;
return n * recursive(n);
}답: 리턴 값으로 자기 자신을 계속 호출하기 때문이다.
6) 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n) {
printf("recursive(%d)\n", n);
return n * recursive(n-1);
}답: 함수 종료 조건이 없기 때문이다. (순환을 멈추지 않는다.)
7) 다음 함수를 sum(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라
int sum(int n) {
printf("%d\n" n);
if (n < 1) return 1;
else return (n + sum(n-1));
}답: (출력내용: 5 4 3 2 1 0, 반환값: 16)
8) 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라
int recursive(int n) {
printf("%d\n" n);
if (n < 1) return 2;
else return (2 * recursive(n-1) + 1);
}답: (출력내용: 5 4 3 2 1 0, 반환값:95)
9) 다음 함수를 recursive(10)로 호출하였을 때, 화면에 출력되는 내용과 함수의 반환값을 구하라
int recursive(int n) {
printf("%d\n" n);
if (n < 1) return -1;
else return (recursive(n-3) + 1);
}답: (출력내용: 10 7 4 1 -2, 반환값:3)
10) 다음 함수를 recursive(5)로 호출하였을 때, 화면에 출력되는 내용을 쓰시요
int recursive(int n) {
if(n != 1) recursive(n-1);
printf("%d\n" n);
}답: 1 2 3 4 5
11) 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 갯수는?
답: ******* 7개
12) 다음과 같은 함수를 호출하고 "recursive" 문자열을 입력한 다음, 엔터키를 눌렀다면 화면에 출력되는 것은?
unknown() {
int ch;
if ((ch = getchar()) != '\n')
unknown();
putchar(ch);
}답: evisrucer
13) 다음을 계산하는 순환적은 프로그램을 작성하시오.
답: $ 1 + 2 + 3 + \cdots + n $
int sum(int n) {
if (n == 1) return 1;
else return (n + sum(n-1));
}14) 다음을 계산하는 순환적은 프로그램을 작성하시오.
답: $ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} $
double SumFraction(int n) {
if (n == 1) return 1;
else return SumFraction(n-1) + (double)1/n;
}15) 순환 호출되는 것을 이해하기 위하여 fib 함수를 다음과 같이 바꾸어서 실행하여 보라. fib(6)을 호출할 때 화면에 출력되는 내용을 쓰시오.
int fib(int n) {
printf("fib(%d) is called\n", n);
if (n == 0) return 0;
if (n == 1) return 1;
return (fib(n-1) + fib(n-2));
}답:
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) {
if (n ==1 ) return 1;
else return (n + sum(n-1));
}답:
int sum(int n) {
int result = 0;
for (int i = 1; i <= n ; i++) {
result += i;
}
return result;
}17) 이항계수(Binomial Coefficient)를 계산하는 순환함수를 작성하라. 이항계수는 다음과 같이 순환적으로 정의된다. 반복함수로도 구현하라.
$$ {_nC_k} = \begin{cases} _{n-1}C_{k-1} + {_{n-1}C_{k}} ( \text{ if } 0 < k < n) \\ 1 ( \text{ if } k = 0 \text{ or } k = n ) \end{cases}$$
// 순환
int binomial(int n, int k)
{
if (k == 0 || n == 1) return 1;
else return binomial(n - 1, k - 1) + binomial(n - 1, k);
}//반복
int binomial(int n, int k)
{
int x, y, z;
for(int i = 0; i < n; i++)
x *= i;
for(int i = 0; i < k; i++)
y *= i;
for(int i = 0; i < n-k; i++)
z *= i;
return x / (y * z);
}18) Ackermann 함수는 다음과 같이 순환적으로 정의된다.
$A(0, n) = n + 1$
$A(m, 0) = A(m-1, 1)$
$A(m, n) = A(m-1, A(m, n-1)) \ m, n >= 1$
18-a) $A(3, 2)$와 $A(2, 3)$의 값을 구하시오.
답: $A(3, 2) = 29$, $A(2, 3) = 9$
18-b) Ackermann 함수를 구하는 순환적인 프로그램을 작성하시오.
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));
}18-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(2^n)$)이 반복 피보나치 수열($O(n)$)보다 많은 계산을 반복하기에 수행시간이 길다.
20) 순환호출에서는 순환호출을 할 때마다 문제의 크기가 작아져야 한다.
20-1) 팩토리얼 계산 문제에서는 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?
답: $n!$에서 n의 크기가 1씩 작아진다.
20-2) 하노이의 탑에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?
답: 원판 하나가 이동되며 나머지 원판에서 순환호출이 일어나며 작아진다.
21) 컴퓨터 그래픽에서의 영역 채우기 알고리즘은 순환 기법을 사용한다. 영역 채우기란 다음과 같은 흰색 영역이 잇을 때 이 영역을 특정한 색으로 채우는 것이다. 순환 호출을 어떻게 사용할 수 있을까? 영역 안의 한 점이 좌표가 주어졌을 경우에 안쪽을 채우는 순환호출 함수를 작성하여 보라
#define WHITE 0
#define BLACK 1
#define YELLOW 2
int screen[WIDTH][HEIGHT];
//
char read_pixel(int x, int y) {
return screen[x][y];
}
//
void write_pixel(int x, int y, int color) {
screen[x][y] = color;
}
//영역 채우기 알고리즘
void flood_fill(int x, int y) {
if (read_pixel(x, y) == WHITE) {
write_pixel(x, y, BLACK);
// 동서남북으로 움직인다.
flood_fill(x + 1, y);
flood_fill(x - 1, y);
flood_fill(x, y + 1);
flood_fill(x, y - 1);
}
}