피보나치 수열

1. 개요

2. 유래

3. 일반항의 유도

4. 성질

5. 음의 피보나치 수열

6. 유리수에서

7. 활용

7.1. 경우의 수

8. 알고리즘

• 반복문 형태의 알고리즘

#!syntax cpp
unsigned int fibonacci_iter(unsigned int n) {

    if (n <= 1) return n; // n이 1보다 작을 때는 해당 값을 그대로 반환한다.
    else {

        int result = 0;
        int iterA = 0, iterB = 1;

        for (int i = 2; i <= n; i++) {

            result = iterA + iterB;
            iterA = iterB;
            iterB = result;

        } // n항의 값을 구한다.

        return result;

    }
	
}

• 재귀 형태의 알고리즘

#!syntax cpp
unsigned int fibonacci_rcsv(unsigned int n) {

    if (n <= 1) return n; // n이 1보다 작을 때는 해당 값을 그대로 반환한다.
    else return fibonacci_rcsv(n - 2) + fibonacci_rcsv(n - 1);
	
}

8.1. 분할 정복을 이용한 알고리즘 [math(\mathcal{O}(\log n) )]

• n-1의 이진법 표기의 각각 자리수들을 역순으로 나열한 배열 binarr을 만든다. [10]
• [math(M^{2^i})]의 값들을 담을 빈 동적 배열 m_powers를 만든 후, 첫 번째 자리에 [math(M)]을 넣는다.
• m_powers의 맨 뒤에 m_powers[-1][11]의 제곱을 추가하는 작업을, m_powers의 길이가 binarr의 길이와 같아질 때까지 반복한다. 이 작업이 완료되면, binarr[i]는 [math(M^{n-1})]을 만들기 위해 m_powers[i]가 곱해져야 할 지의 여부를 나타내게 된다.
• 2x2 단위행렬 final_mat를 만든다.
• 정수 i가 0에서 len(binarr)-1이 될 때까지 1만큼 증가시키며, 다음을 반복한다:
• 만약 binarr[i] == 1이라면, final_mat에 m_powers[i]를 곱한다.
• final_mat[0][0]이 [math(F_n)]이다.

#!syntax python
from math import log2

def matmul_2x2(a, b):
    # 2x2 행렬 곱셈
    return_mat = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                return_mat[i][j] += a[i][k] * b[k][j]
    
    return return_mat

def to_reverse_bin(n: int):
    return_array = [0 for _ in range(int(log2(n))+1)]
    while n > 0:
        temp_lg2n = int(log2(n))
        return_array[temp_lg2n] += 1
        n -= 2 ** temp_lg2n
    
    return return_array

def fib(n: int):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    binarr = to_reverse_bin(n-1) 
    # 또는 python의 내장 라이브러리 함수 bin()을 이용하여
    # binarr = list(map(int, reversed(bin(n-1)[2:])))

    m_powers = []
    m_powers.append(
        [[1, 1],
        [1, 0]]
    )

    for i in range(1, len(binarr)):
        m_powers.append(matmul_2x2(m_powers[-1], m_powers[-1]))
    
    final_mat = [
        [1, 0],
        [0, 1]
    ]
    for i in range(len(binarr)):
        if binarr[i]:
            final_mat = matmul_2x2(m_powers[i], final_mat)

    return final_mat[0][0]

if __name__ == "__main__":
    print(fib(1000000))

9. 여담

• 수1의 수학적 귀납법에 이 내용이 포함되어 있어 1997학년도 대학수학능력시험, 2004학년도 4월 교육청 모의고사에 피보나치 수열과 관련된 문제를 출제하기도 했었다. 이후 한동안 등장도 안하다가 2023학년도 수능 15번에 출제되었고, 이어서 2023년에 치러진 3월 학력평가 15번에도 등장했다.

• 치킨과의 상관관계
  인터넷 상에서 피보나치 수열이 치킨수([math(F_{n-1})])와 먹을 사람수([math(F_n)])와의 관계를 나타내는데 적절하다는 설이 있다. 이는 한 사람이 여유있게 먹을 수 있는 치킨의 양이 1인분에 약간 못 미치며, 한 마리를 다 뜯기에는 배부르기 때문이다.[12]1인1닭이 가능한 사람들이라면 굳이 신경쓸 필요 없다.

#!syntax python
def FibonaChicken(N):
    if N <= 2:
        return 1
    i = inverse_fibonacci(N)
    if is_fibonacci(N):
        return Binet(i - 1)
    else:
        while N > Binet(i):
            i += 1
        return Binet(i - 2) + FibonaChicken(N - Binet(i - 1))

10. 관련 문서

• 수열
• 황금비