- 1 -
데이터 구조 실습 (3주차)
2021. 3. 17
학번: 이름:
[문제 1] 다음에 답하시오.
a. 다음 C 함수는 올바르게 동작하는가?
int recursive(int n) { if ( n == 1)
return 0;
else
return n + recursive(n);
}
b. 다음 함수를 recursive(20)으로 호출시 반환되는 값은 무엇인가?
int recursive(int n) { if ( n <= 0 )
return 0;
else
return recursive(n-3) + n;
}
c. 다음과 같이 1부터 n까지의 합을 구하는 순환적 알고리즘, sum(n)을 작성하라. 또한, 이 알고리즘을 C 함 수로 작성하라. 또한, 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실 행시켜라.
1+ 2 + 3 + 4 + .... + n
d. 1부터 n까지의 짝수의 합을 구하는 순환적 알고리즘, addEven(n)을 작성하라. 또한, 이 알고리즘을 C 함 수로 작성하라. 또한, 사용자로부터 n을 입력받아서 작성된 함수를 테스트하는 main() 함수를 작성하고 실 행시켜라.
- 2 - [문제 2] 피보나치 수열은 다음과 같이 정의된다.
fibo(n) = 0 n = 0
1 n = 1
fibo(n-1) + fibo(n-2) n>= 2
a. n에 대한 피보나치 수를 구하여 반환하는 알고리즘 fibo_rec(n)을 순환적으로 작성하라.
b. a)에서 작성한 알고리즘을 C 함수로 작성하라.
c. n에 대한 피보나치 수를 구하여 반환하는 a)의 반복적 버전, fibo_iter(n)을 작성하라.
d. 다음의 n 값에 대해서 a), b)의 두 함수에 대해서 실행 시간을 측정하여 다음 테이블을 완성하라. 또한, 그 결과를 그래프로 그려라.
n 10 15 20 25 30 35 40 45
fibo_rec()
fibo_iter()
