피보나치수열, c언어, 재귀함수, 자료구조

소개글

자료구조론 과제에서 만점 받은 과제입니다
피보나치수열은 c언어로 구현한 리포트입니다

목차

1. 문제
➊ 재귀 프로그램
➋ 반복 프로그램

2. 문제풀이 방법(IDEA) 및 알고리즘(ALGORITHM)
➊ Main Function
1) recursive_fibo Function
2) Iterative_fibo Function

3. Program

4. 입출력의 예 및 수행 결과
➊ 입력 값에 따른 올바른 출력 값
➋ 실제 출력 결과

5. 결과 분석 및 토의

6. 참고 : source code

본문내용

❏ 문제 : 주어진 양의 정수값 N에 대해 피보나치 수 Fn 을 계산하는
(1) 재귀 프로그램과 (2) 반복 프로그램을 각각 작성하여, 다음 N = 0, 1, 5, 10, 15, 20, …값에 대한 피보나치 수를 출력하고 수행시간을 조사한다.

➊ 재귀 프로그램
재귀 함수를 이용하여 피보나치 수를 구할 수 있다.
Fib(n) = Fib(n-1) + Fib(n-2)
->이 함수를 이용하여 피보나치 수를 구할 경우, 피보나치 함수를 그대로 이용하여 문제 해결은 용이하나, 시간과 공간의 비효율성으로 수행시간이 반복 프로그램보다 더 걸릴 것으로 예상된다.
->Tr(n) = Tr(n-1) + Tr(n-2) + 1 (if n >= 2)

➋ 반복 프로그램
반복문(for loop)을 이용하여 피보나치 수를 구한다. 직관적으로 이해하기 편하고 연산이 재귀보다 적으므로 수행시간이 재귀 프로그램보다 덜 걸릴 것이다.

❏ 문제 풀이 방법(IDEA) 및 알고리즘(ALGORITHM)
➢ Main Function
사용자가 구하고 싶은 피보나치 수를 임의로 입력하게 한 다음, 그 N에 대하여 두 프로그램을 차례로 시행하게 한다. 재귀 함수 결과를 먼저 출력한 후, 시행 시간을 재어서 수행 시간 경과도 같이 나타냈다. 그리고 반복 함수도 같은 방식으로 불러들여, 똑같이 시행하였다. 문제에서 주의할 점은, N이 1만큼 증가하는 것이 아니라, 0, 1, 5, 10, … 로 처음 0, 1을 제외하고 5의 배수로 증가한다. 그래서 0, 1은 따로 취급하고 5의 배수는 나머지 연산자를 이용하여 구하였다.

➊ recursive_fibo Function
재귀 프로그램을 시행하는 함수이다. 먼저 N 이 0, 1이면 각각의 N 값을 그대로 받고, 그렇지 않은 경우에는 피보나치 원리를 이용한 재귀함수를 이용해서 recursive_fibo(num-1) + recursive_fibo(num-2)을 return값으로 받아, 시스템적으로 stack에 저장하여 연산을 수행하게 된다.

참고 자료

없음