Script Programming(스크립트 프로그래밍)

피보나치 수열이 0 이상의 정수 n에 대하여

         선형점화공식(linear recurency):  f(n) = f(n - 1) + f(n - 2) 과

         과 초기조건(initial condition):  f(0) = 0,  f(1) = 1

로 정의된 수열인데 이를 음의 정수 n에 대하여도 위의 점화공식을

             f(n) = f(n + 2) - f(n + 1)     (∀ n = -1, -2, -3, -4, -5, ...)

로 고쳐 축차 적용하여 얻어지는 수열

   f(-1), f(-2), f(-3), f(-4), f(-5), ....

을 네가보나치 수열(negabonacci sequence)이라고 한다.

   즉,

             f(-1) = f(1) - f(0) = 1 - 0 = 1

             f(-2) = f(0) - f(-1) = 0 - 1 = -1

             f(-3) = f(-1) - f(-2) = 1 - (-1) = 2

             f(-4) = f(-2) - f(-3) = -1 - 2 = -3

             f(-5) = f(-3) - f(-4) = 2 - (-3) = 5

             f(-6) = f(-4) - f(-5) = -3 - 5 = -8

             ..............................................

피보나치 수열는 피보나치가 토끼의 성장과 번식을 관찰하다가 발견한 수열이라고 합니다.

피보나치 수(Fibonacci number)의 정의는 간단합니다.

0과 1로 시작해서 덧셈을 계속 이어가면 얻어지는 수들입니다.

     0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ......

초항을 제 0항으로 하고 제 0항, 제 1항, 제 2항, ...... 순으로 나열하면

    F(0),  F(1),  F(2),  F(3),  F(4), F(5),  F(6),  F(7),  F(8),  F(9),  F(10), ......

이 되고, 번호를 괄호 속에 넣지 않고 우측 첨자로 붙여 나열하면,

    F₀,  F₁,  F₂,  F₃,  F₄,  F₅,  F₆,  F₇,  F₈,  F₉,  F₁₀, ......

이 됩니다.  즉, 

                  F₀ = F(0) = 0

                  F₁ = F(1) = 1

                  F₂ = F(2) = 1

                  F₃ = F(3) = 2

                  F₄ = F(4) = 3

                  F₅ = F(5) = 5

                  F₆ = F(6) = 8

                  F₇ = F(7) = 13

                  F₈ = F(8) = 21

                  F₉ = F(9) = 34

                  F₁₀ = F(10) = 55

                   ........................

피보나치 수들을 점화공식(recurrence formula)으로 정의하면

        F(n) = F(n - 1) + F(n - 2)     ∀ n = 2, 3, 4, 5, ...

        F(0) = 0,  F(1) = 1

가 됩니다.

            0 + 1 = 1

            1 + 1 = 2

            1 + 2 = 3

            2 + 3 = 5

            3 + 5 = 8

            5 + 8 = 13

             ..........

위의 점화공식  F(n) = F(n - 1) + F(n - 2)  은 

               F(n) - F(n - 1) = F(n - 2) 

혹은

               F(n) - F(n - 2) = F(n - 1) 

으로 사용되어지기도 합니다.