마스터 누누

[알고리즘] 재귀함수 - 피보나치 수열 본문

알고리즘/알고리즘 강의

[알고리즘] 재귀함수 - 피보나치 수열

마스터누누 2017.04.18 20:14

재귀함수 - 피보나치 수열



피보나치 수열은 다음과 같다.

1,1,2,3,5,8,13,21,34,55,89,144,233,377...

즉, n+2항은 바로 뒤 2개의 항의 합으로 결정되는 구조이다.





1. 재귀함수 피보나치 수열

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
 
int main() {
    
    int num, result;
 
    scanf_s("%d"&num);
    result = fibo(num);
    printf("%d", result);
 
    return 0;
}
 
int fibo(int num) {
    
    if ((num == 1)||(num==2)) {
        return 1;
    }
 
    return fibo(num - 1+ fibo(num - 2);                                                                  
}
 
cs


위의 점화식을 재귀함수로 구현하였다.

n+2가 아닌 n을 구해야하기 때문에 양변의 n값에 -2를 하였다. 

또한 num이 첫째항이거나 둘째항일때 1을 반환하도록 했다.





2. 메모이제이션(Memoization) 피보나치

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
 
#define Capa 100
 
int main() {
    
    int num, result;
 
    scanf_s("%d"&num);
    result = fibo(num);
    printf("%d", result);
 
    return 0;
}
 
int fibo(int num) {
    
    int buf[Capa];
 
    if (buf[num] > 0) {
        return buf[num];
    }
    if ((num == 1)||(num==2)) {
        return buf[num] = 1;
    }
 
    return buf[num] = fibo(num - 1+ fibo(num - 2);                                                       
}
 
cs


다음은 메모이제이션으로 피보나치를 구현한 코드이다.

아래의 fibo 함수를 보면 1차원 행렬을 이용하여 계산된 값이 저장되는 것을 볼 수 있다.

이를 활용하면 앞에서 포스팅한 내용과 마찬가지로 불필요한 계산을 줄여

연산 속도를 높일 수 있다.



저작자 표시
신고
1 Comments
댓글쓰기 폼