피보나치 수열

 

0. 문제 

코드업 1855 피보나치 수열

https://codeup.kr/problem.php?id=1855

[기초-재귀함수] 재귀로 n번째 피보나치 수 리턴하기

1. 설계 & 분석

메인함수와 피보나치 수열 정의 함수 2개로 나눴음.

2. 순서도

main

Fibonacci

 

result = Fibnonacci(n-2) + Fibonacci(n-1) 

rescursive Loop FlowChart는 그리는 사람마다 방식이 조금씩 달랐다.

 

원래 디자인 문서와 순서도는 제 3자가 구현해 낼 수 있으면 잘 그린거라고 했다.

나는 아닌가?!??!

 

main + fibonacci

 

 

3. 구현

#include <stdio.h>
 
unsigned int Fibonacci(unsigned int n)
{
    unsigned result = 1;
    
    if(n <= 2)
    {
    result = 1;
    }
    else
    {
        result = Fibonacci(n-2) + Fibonacci(n - 1 );
    }
    
    return result;
} 
 
int main(void)
{    
    unsigned int n = 0, result = 0;
    scanf("%d", &n);
    
    printf("%d ",Fibonacci(n));
    
    return 0;
}

in C

 

#include <iostream>
using namespace std;
 
unsigned int Fibonacci(unsigned int n)
{
    unsigned result = 1;
    
    if(n <= 2)
    {
    result = 1;
    }
    else
    {
        result = Fibonacci(n-2) + Fibonacci(n - 1 );
    }
    
    return result;
} 
 
int main(void)
{    
    unsigned int n = 0, result = 0;
    cin >> n;
    
    cout << Fibonacci(n) <<endl;
    
    return 0;
}

in C++

 

 

4. 시간복잡도 분석

 

Lower Bound: O(2^n/2)

Upper Bound: O(2^n)

 

5. 재귀가 아닌 Dynamic Programming 기법으로 구현하는 피보나치

https://m-falcon.tistory.com/118

피보나치 수열 2 (Memoization, Dynamic Programming ver)