- 1 -
데이터 구조 실습 (3주차)
2021. 3. 17
학번: 이름:
[문제 1] 다음에 답하시오.
a. 다음 C 함수는 올바르게 동작하는가? 여러분 답변에 그 이유를 주시오.
int recursive(int n) { if ( n <= 1) // base part
return 0;
else
return n + recursive(n); // recursive part: 문제 크기가 반드시 줄어들어야 한다 }
- 2 -
b. 다음 함수를 recursive(20)으로 호출시 반환되는 값은 무엇인가?
int recursive(int n) { if ( n <= 0 )
return 0;
else
return recursive(n-3) + n;
}
recursive(20) -> recursive(17) + 20 -> recursive(14) + 17 -> recursive(11) + 14 -> recursive(8) + 11 0+2+5+8+11+14+17+20 0+2+5+8+11+14+17 0+2+5+8+11+14 0+2+5+8+11 0+2+5+8 -> recursive(5) + 8 -> recursive(2) + 5 -> recursive(-1) + 2 -> 0
0+2+5 0+2 0 + 2
- 3 -
c. 다음과 같이 1부터 n까지의 합을 구하는 순환적 알고리즘, sum(n)을 작성하라. 또한, 이 알고리즘을 C 함 수로 작성하라. 또한, 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실 행시켜라.
1+ 2 + 3 + 4 + .... + n = 1+ 2 + 3 + 4 + .... (n-1) + n
sum(n) sum(n-1)
1) 문제를 순환적으로 정의하시오.
sum(n) = 0 n =0 sum(n-1) + n n>=1
2) 1)을 이용하여 순환적 알고리즘을 작성하라.
sum(n) {
if n <=0 then return 0 else
return sum(n-1) + n endif
}
3) 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실행시켜라.
테스트 데이터: 10 => 55 0
-5
- 4 -
d. 1부터 n까지의 홀수의 합을 구하는 순환적 알고리즘, addOdd(n)을 작성하라. 또한, 이 알고리즘을 C 함 수로 작성하라. 또한, 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실 행시켜라.
1) addOdd(n)에 대한 순환적 정의를 주라.
addOdd(n) = 0 if n <=0 addOdd(n-1) if n %2 =0 n+ addOne(n-2) otherwise
2) addOdd(n)에 대한 순환적 알고리즘을 작성하라.
addOdd(n) {
if n <=0 then return 0 else if n %2 = 0 then
return addOdd(n-1) else
return n + addOdd(n-2) endif
}
3) 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실행시켜라.
- 5 - [문제 2] 피보나치 수열은 다음과 같이 정의된다.
fibo(n) = 0 n = 0
1 n = 1
fibo(n-1) + fibo(n-2) n>= 2
a. n에 대한 피보나치 수를 구하여 반환하는 알고리즘 fibo_rec(n)을 순환적으로 작성하라.
fibo_rec(n) {
if n = 0 then return 0 else if n= 1 then return 1 else
return fibo(n-1) + fibo(n-2) end if
}
b. n에 대한 피보나치 수를 구하여 반환하는 a)의 반복적 버전, fibo_iter(n)을 작성하라.
fibo_iter(n) {
if n = 0 then return 0 else if n= 1 then return 1 else
prev <- 0 curr <- 1
for i <-2 to n do next <- prev + curr prev <- curr curr <- next repeat
return curr end if
}
c. a), b)에서 작성한 알고리즘을 각각 C 함수로 작성하라.
- 6 -
d. 다음의 n 값에 대해서 a), b)의 두 함수에 대해서 실행 시간을 측정하여 다음 테이블을 완성하라. 또한, 그 결과를 그래프로 그려라.
n 10 15 20 25 30 35 40 45
fibo_rec()
fibo_iter()
