프로그래밍 실습 단골 문제로 등장하는 아주 유명한 문제인 피보나치 수열을 다룰 것이다. 수학 쪽이나 디자인 학과에서도 이 피보나치 수열에 대해 언급하는 일이 잦다. 자연에서 흔히 찾을 수 있는 수열이라고 하더라. 그만큼 이 피보나치 수열 자체를 연구하는 일도 많다. 내가 초등학생 때 영재원 다니면서 초등학교 수학/과학 탐구 보고서 주제로도 자주 등장했다. 일단 피보나치 수열의 정의를 링크들 ( 위키백과 , 나무위키 ) 를 통해 한 번 알아보자.
우선 시작은 피보나치 수열에 대해 알아보는 것이다. 다음 문제를 통해 피보나치 수를 찾아보자.
[문제]
숫자 n을 입력받아 n 번째 피보나치 수를 출력하라. 단, 수열의 시작은 0, 1 이다.
[예시]
입력: 5
출력: 3
해설: 0 1 1 2 3 이므로 5번째인 3을 출력
입력: 19
출력: 2584
해설: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 이므로 19번째인 2584를 출력
황금비 이야기 ( 삼천포로... )
피보나치 수열이 나아가면서 인접한 수열 쌍의 비는 황금비에 접근한다. 우리가 생활 속 미학에 대한 정보를 접할 때 황금비에 대한 이야기는 빼놓을 수 없다. 인공조형물이 황금비를 이뤘기 때문에 아름다운 것인지, 아름답게 만들고 보니 황금비를 이루는 것인지는 논란의 여지가 있다. 다만 자연의 많은 현상들이 황금비를 이루는 것은 살펴볼 수 있다. 자연 속에서 발견되는 피보나치 수열과 인공 조형물에서 발견되는 황금비에 대해 살펴보자.
1. 동물의 번식
주로 토끼를 통해 이 예시를 접하게 된다. 피보나치 수가 처음 문헌에 등장한 것은 기원전 5세기 인도에서 였다곤 하지만 우리가 피보나치 수라고 부르는데서 알 수 있듯 사람들은 1202년 토끼의 번식을 연구하면서 언급하게 된다. 왼쪽 사진의 토끼들은 네 가지 규칙을 가지고 번식한다.
- 최초엔 새로 태어난 토끼들만 1쌍이 있다.
- 토끼들은 태어난 지 2달이 되면 번식할 수 있다.
- 번식이 가능한 토끼 1쌍은 매 달 새끼 1쌍을 낳는다.
- 토끼는 죽지 않는다.
이 조건에서 토끼들은 피보나치 수열을 이루며 증가한다.
2. 소라 고동의 모양
위 사진과 같이 중심에서 뻗어나갈때 소라 고동은 피보나치 수열을 이루며 성장한다. 즉 계속해서 황금비를 이루며 성장하는 꼴이다.
3. 비너스 조각상
전세계인의 사랑을 받는 비너스 조각상도 신체 전체적으로 황금비를 이루는 한편 부분적으로도 황금비를 이룬다.
4. 기타 등등
이외에도 해바라기 꽃잎의 개수, 나무가지 뻗침 등의 예시에서도 살펴볼 수 있다.
전산학부, 컴퓨터 공학과가 배우는 피보나치 ( 삼천포 again )
이 이야기는 나중에 내가 더 공부하게 되면 자세히 포스팅할 기회가 있을 것이다. 오늘 알아볼 것은 단순히 피보나치 수열을 출력하는 정도의 수준이다. 재귀함수를 처음 배우면서 실습과제로 정말정말정말 많이 나오는 문제인 만큼 매우 간단한 수준이다. 나중엔 전공 과목 중에 알고리즘 시간에 접했던 피보나치 힙 자료구조들도 있었다.
'Study > Python' 카테고리의 다른 글
| Pythagorean Expectation ( ACM-ICPC 교내 예선 ) (0) | 2015.10.27 |
|---|---|
| 계승 ( 팩토리얼 ) 계산하기 ( n!, factorial number ) (0) | 2015.10.26 |
| 3n+1 문제 (0) | 2015.10.25 |
| 진법 변환기 (Base Radix Converter) (0) | 2015.10.25 |
| 최대공약수 구하기 (Great Common Division, GCD) (0) | 2015.10.25 |