강의실/정보영재

피보나치 수열은 죽지 않는 토끼에서 유래 되었는데요.

처음 태어난 토끼 한쌍은 한달이면 다 자라고 그 다음달 부터는 매달 한쌍의 새끼를 낳았을때 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회 의 계산으로 피보나치 수열의 값을 계산 할 수가 있게 됩니다.)

 

피보나치 수열을 계산하는 방법이 행렬식을 이용한 방법만 있는 것은 아니지만...

이렇게 행렬식을 이용해서 피보나치 수열을 풀어 나갈 수 있다는 것을 발견한 사람도 대단한것 같아요.^^

 

우리 학생들도 많은 연구를 통해서...

아직 밝혀지지 않은 많은 경우를 직접 찾아 내서 미래의 기술 발전에 큰 이바지를 할 수 있는 학생들이 되기를 기원합니다.

 

인천 서구 원당컴퓨터학원

 

8 0
  • 잉여토기 2019.10.15 16:23 신고    

    피보나치 수열로 점점 줄어드는 숫자의 정렬 기준이 있어보이네요.

  • 2019.10.15 17:42    

    비밀댓글입니다

  • 휴식같은 친구 2019.10.15 19:46 신고    

    정말 피보나치 수열을 발견한 사람이 대단하네요.ㅎㅎ
    잘 보고 갑니다.

  • 버블프라이스 2019.10.16 05:05    

    저는 좀 어렵네요
    행렬의 곱을 이용한 피보나치 수열 구하는 방법을 잘 보고 배우고 갑니다^^ 즐거운 수요일 되세요

  • 핑구야날자 2019.10.16 06:43    

    피보나치는 참 오랜만에 들어 봅니다 오늘도 즐거운 하루 보내세요

  • 공수래공수거 2019.10.16 08:34 신고    

    밝혀지지 않은것들을 우리 나라 사람들이 밝혀 내면 좋죠.ㅎ

  • *저녁노을* 2019.10.16 08:44 신고    

    와...어려운데요.
    ㅎㅎ
    우리 아이들에게 기대 걸어봅니다.