피보나치 수열은 죽지 않는 토끼에서 유래 되었는데요.
처음 태어난 토끼 한쌍은 한달이면 다 자라고 그 다음달 부터는 매달 한쌍의 새끼를 낳았을때 1년 후 혹은 2년 후에 몇쌍이 되어 있는지 궁금해서 묻는 문제에서 유래 되었는데요.
이러한 토끼가 살아 있는 쌍을 구하는 공식을 테이블을 이용해 그려 보면 다음과 같이 그려 볼 수가 있습니다.
새끼를 낳을수 있는 토끼를 성체라고 보면 다음과 같이 됩니다.
기간 | 1월 | 2월 | 3월 | 4월 | 5월 | 6월 | 7월 | 8월 | 9월 |
태어난쌍 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
성체 | 0 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
살아있는쌍 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
성체를 계산 하는 방법은 전월의 성체의 수에 전전월에 태어난 토끼의 수를 더해 주면 됩니다.
가령 3월의 성체 수는 2월의 성체수(0) + 1월에 태어난 쌍(1) = 1 이 되고
4월의 성체 수는 3월의 성체수(1) + 2월에 태어난 쌍(0) = 1 이 되는 이치입니다.
성체는 새끼를 낳을 수 있으므로 해당 월에 태어나는 토끼는 해당월의 성체수에 해당 합니다.
따라서 살아있는 쌍은 전월에 살아있는 쌍의 수 + 해당월에 태어난 수가 살아 있는 쌍이 됩니다.
이렇게 계산을 해 보면 결국은 해당월에 태어나는 수는 전전월에 살아있는 수와 동일하게 되는데요.
이러한 테이블을 이용해서 n개월 후의 토끼의 수는 n-1개월 후의 토끼 수 + n-2개월 후의 토끼 수가 되며
점화식으로는 f(1)=1,f(2)=1 이고 f(n) = f(n-1) + f(n-2) 로 표현을 할 수가 있습니다.
이 때 수열의 일반항 f(n)을 구하는데 이 수열을 행렬을 통해 An+1,An 에 관한 식으로 표현이 가능합니다.

여기서 행렬의 곱셈식을 살펴 보면 다음과 같습니다.

따라서 행렬식을 통해 An+1 = An + An-1 을 표현해 볼 수가 있는데요.
이것은 다시 다음과 같이 표현을 해 볼 수가 있습니다.

이렇게 가면 결국은 다음과 같이 표현을 해 볼 수가 있게 됩니다.

결국은 다음과 같이 표현을 할 수가 있습니다.

따라서

이렇게 표현을 할 수가 있으며 행렬의 곱셈식을 이용해서 다음과 같이 표현이 가능합니다.


이 행렬의 곱을 이용한 피보나치 수열을 계산하게 되면
https://www.acmicpc.net/problem/2749의 피보나치3 과 같은 n의 값이 큰 데이터도 분할 정복 기법을 이용해서 풀이를 해 볼 수가 있습니다.
가령 n의 값이 10000 의 값이 들어 온다면

위와 같이 계산을 하게 되면 10000 -> 5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 (18회 의 계산으로 피보나치 수열의 값을 계산 할 수가 있게 됩니다.)
피보나치 수열을 계산하는 방법이 행렬식을 이용한 방법만 있는 것은 아니지만...
이렇게 행렬식을 이용해서 피보나치 수열을 풀어 나갈 수 있다는 것을 발견한 사람도 대단한것 같아요.^^
우리 학생들도 많은 연구를 통해서...
아직 밝혀지지 않은 많은 경우를 직접 찾아 내서 미래의 기술 발전에 큰 이바지를 할 수 있는 학생들이 되기를 기원합니다.
인천 서구 원당컴퓨터학원
'강의자료 > 정보영재' 카테고리의 다른 글
공부 잘하는 방법 (282) | 2019.11.28 |
---|---|
Code Block 디버그 오류(For MinGW compilers, it's 'gdb.exe') (295) | 2019.11.21 |
행렬식의 기하학적 의미 - 벡터가 이루고 있는 평행사변형의 넓이 (10) | 2019.09.27 |
[컴퓨팅 사고력]2의 보수 3의 보수는 무엇일까? (8) | 2019.09.23 |
CodeBlock 환경설정 초기화 방법 (7) | 2019.09.18 |