[C 언어] 피바나치(Fibonacci)의 수열 통항(귀속법, 비귀속법)을 구한다.

이탈리아의 수학자 레오나르도 페보나치가 1202년 토끼의 새끼 출산 문제를 연구하던 중 이 수열을 발견했다. 큰 토끼 한 쌍이 매달 한 쌍씩 새끼 토끼를 낳았는데, 새끼 토끼 한 쌍이 태어난 지 한 달이 지난 후에 또 새끼를 낳았는데, 만약 토끼가 죽지 않는다면: 토끼 한 쌍이 1년에 몇 쌍으로 번식할 수 있겠는가?제목에는 본질적으로 두 종류의 토끼가 있다. 하나는 생식할 수 있는 토끼로 줄여서 큰 토끼라고 한다.새로 태어난 토끼는 생식할 수 없으며, 줄여서 작은 토끼라고 부른다.작은 토끼는 한 달 만에 큰 토끼로 자란다. 큰 토끼와 작은 토끼의 합계를 구한다.
월 Ⅰ III IV V VI VI VIIIX X X X X X X X 1 2 3 5 8 13 21 34 55 89 144 새끼 토끼 0 1 1 2 3 5 8 13 21 34 55 89 ~ 10 2 월 큰 토끼 144 쌍, 작은 토끼 89 쌍, 총 토끼 144 + 89 = 233 쌍
① 매월 토끼 대수 = 매월 큰 토끼 대수.② 매월 큰 토끼 대수는 지난달의 큰 토끼 대수와 작은 토끼 대수의 합이다. 종합해 보면 ① ② 두 가지를 보면 우리는 매월 큰 토끼 대수는 두 달 전의 큰 토끼 대수의 합과 같다.
만약 un으로 n월의 토끼 대수를 표시한다면 un=un-1+un-2, n>2의 매달 토끼 대수 un을 수열로 배열하면 1,1,2,3,5,8,13,21,34,55,89144이다. 이 수열을 피보나치 수열이라고 한다.
귀속법:
공식 f[n]=f[n-1]+f[n-2]를 사용하여 순서대로 귀속 계산을 하고 귀속 종료 조건은 f[1]=1, f[2]=1이다.
코드 예:
#include<iostream>
using namespace std;

long long Fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else if(n > 1)
    {
        return Fib(n - 1) + Fib(n - 2);
    }
    //return n > 1 ? Fib(n - 1) + Fib(n - 2) : n; //       ,      
}

void Test()
{
    int N = 0;
    scanf("%d", &N);
    int ret = Fib(N);
    printf("%d
", ret); } int main() {     Test();     system("pause");     return 0; }

그러나 귀속법은 이 문제를 해결하는 것이 효율적이지 않다. 다음은 비귀속법을 살펴보자.
비귀속법:
교체 실현이 가장 효율적이고 시간 복잡도는 n*1=0(n)이며 공간 복잡도는 0(1)이다.
#include<iostream>
using namespace std;

long long Fib(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else if (n > 1)
    {
        int a = 1;
        int b = 1;
        int c = 1;
        for (int i = 2; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

void Test()
{
    int N = 0;
    scanf("%d", &N);
    int ret = Fib(N);
    printf("%d
", ret); } int main() {     Test();     system("pause");     return 0; }

좋은 웹페이지 즐겨찾기