로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요. 최신판 당신의 편집 46번째 줄: 46번째 줄: == 같이 보기 ==== 같이 보기 == * [[뤼카 수열]]* [[피보나치 수를 구하는 프로그램]] * [[피보나치 소수]] * [[제켄도르프의 정리]] {{각주}}{{각주}} [[분류:수열]][[분류:수열]] 스팸 방지 검사입니다. 이것을 입력하지 마세요! == 개요 == '''피보나치 수열(Fibonacci sequence)'''은 다음과 같은 [[정수]]의 수열을 말한다. 피보나치 수열의 항은 피보나치 수라고 한다. : 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ([[OEIS]]의 수열 [[oeis:A45|A45]]) 첫항에 0을 포함시키기도 한다. 이것은 처음의 두 수를 0,1로 선택하냐 1,1로 선택하냐의 차이다. [[점화식]]은 다음과 같다. * <math>a_1 = 1, a_2 = 1</math> * <math>a_{n+2} = a_{n+1} + a_n</math> 일반항은 다음과 같다. * <math>a_n = \frac{\phi^n - \psi^n}{\phi - \psi}</math> * <math>\phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2}</math>, <math>\phi, \psi</math>는 <math>x^2 - x - 1 = 0</math>의 해로 큰 쪽이 <math>\phi</math>, 작은 쪽이 <math>\psi</math>이다. == 아이디어 == [[피보나치]]는 다음과 같은 상황을 생각했다. * 첫 달 처음에 갓 태어난 암수 토끼 한 쌍이 있다. * 토끼는 한 달동안 자라 어른 토끼가 된다. * 어른 토끼 한 쌍은 그 달 마지막에 암수 토끼 한 쌍을 낳는다. * {{ㅊ|[[영생|심지어 안죽는다]]}} 그렇다면 매 달 처음에 토끼가 몇 마리나 있을까에 대해 답을 찾다가 발견한 수열이다. == 특징 == === 황금비 === <math>\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = \phi</math>이다. 여기의 <math>\phi</math>는 위의 그거. [[황금비]]라고 부른다. <math> \begin{align} \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} &= \lim_{n \rightarrow \infty} \frac{a_{n+1}+a_n}{a_{n+1}} &= 1 + \frac{1}{\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}} \end{align}</math> 를 이용하면, <math>x = 1+\frac{1}{x}</math> [[방정식]]을 푸는 형태가 되어 구할 수 있다. <ref>잘 보면 첫 항이 뭐냐에 상관없이 황금비로 수렴한다는 것을 알 수 있다.</ref> === n번째 항 계산하기 === <math>A_n = \left[ \begin{array}{cc} a_{n+2} & a_{n+1} \\ a_{n+1} & a_{n} \end{array} \right] </math>이라고 하면, <math>A_{n+1} = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] A_n </math>가 성립한다. <math>a_0 = 0</math>이라고 하면, <math>A_0</math>도 역시 <math> \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] </math>가 된다. 이것들을 이용하면, <math>A_n = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]^{n+1}</math>가 성립함을 알 수 있다. 이 식이 요긴하게 쓸 수 있는데, 큰 <math>n</math>에 대해서 <math>a_n</math>을 구할 수 있기 때문이다. <math>n</math>제곱을 <math>O(\log n)</math>번의 곱셈만에 구할 수 있다는 걸 이용하면 된다. 물론 위에 있는 일반항에 대입해 버리면 되지만, 일반항 쪽은 소수점 계산이 필요하기 때문에 정확한 값을 구하기 쉽지 않지만, {{ㅊ|<math>\mathbb{Q} [\sqrt{5}]</math>를 구현하면 어떨까}} 이것을 이용하면 정확하고 빠르게 값을 계산할 수 있다. 피보나치 수열 뿐만 아니라 [[점화식]]이 그 전 항들의 어떤 선형 합, 즉, <math>a_{n+k} = \sum_{i=0}^{k-1} c_i a_{n+i} </math> 꼴로 나타날 때에는 이런 전개가 가능하다. {{ㅊ|그중 가장 간단한게 이거}} == 프로그래밍 == 프로그래밍 언어를 공부할 때 어떤 함수가 자기 자신을 다시 불러와서 사용하는 재귀함수를 배우면서 간단한 피보나치 수를 구하는 프로그램을 짜보게 되는 경우가 많다. 다만 이때 짜보는 소스 코드는 계산해야하는 값이 늘어나면 이런저런 문제를 일으키므로 현업에서 사용가능한 소스 코드라고 보기는 힘들다. 이에 대한 설명은 [http://hanmomhanda.github.io/2015/07/27/재귀-반복-Tail-Recursion/ 여기]의 글을 읽어보자. ==이걸 써먹거나 응용한 것들== *n명의 사람에게 치킨을 먹일 때 몇 마리를 주문해야하는지 확인하는 일명 [http://fibonachicken.herokuapp.com/ 피보나치킨] == 같이 보기 == * [[피보나치 수를 구하는 프로그램]] {{각주}} [[분류:수열]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:ㅊ (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:취소선 (원본 보기) (준보호됨)