피보나치 계산기

F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2) ⇒ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …; 이웃한 두 항의 비 → φ = (1 + √5) / 2 = 1.6180339887…

F(1) = F(2) = 1

시작값 두 개이며, 이 페이지가 명시적으로 고른 선택입니다. 1부터 세면 F(1)과 F(2)가 모두 1이고 F(10)은 55입니다. 다른 널리 쓰이는 관례는 F(0) = 0, F(1) = 1로 두는데, 그러면 모든 번호가 하나씩 밀려서 다섯 번째 항이 8이 아니라 5가 됩니다. 어느 쪽도 틀리지 않았지만, 두 관례는 모든 항의 번호에서 서로 어긋납니다

F(n) = F(n − 1) + F(n − 2)

점화식이며, 정의의 전부입니다. 각 항이 앞의 두 항을 더한 값입니다. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8입니다. 시작값 두 개에서 앞으로 밀어 나가기 때문에 이 페이지가 열 항을 만들든 천 항을 만들든 같은 값이 듭니다. 풀어야 할 공식이 없고 덧셈이 반복될 뿐입니다

n

원하는 항의 개수이며 2에서 78까지입니다. 아래 끝이 1이 아니라 2인 까닭은 비 출력이 어떤 항과 그 앞 항을 함께 필요로 하기 때문입니다. 항이 하나뿐이면 나눌 대상이 없으므로, 페이지는 빈 비를 인쇄하는 대신 그 요청을 거부합니다. 위 끝은 항들이 평범한 부동소수점 산술에서 더 이상 정확하지 않게 되는 지점입니다

F(78) = 8944394323791464

이 페이지가 닿는 마지막 항이며, 거기서 멈추는 이유입니다. F(79)는 14472334024676221인데, 이는 배정도가 정확히 담을 수 있는 가장 큰 정수인 9007199254740991을 넘어섭니다. 그래서 그 뒤로는 인쇄되는 숫자가 수열의 값이 아니라 근삿값이 됩니다. 페이지는 거의 맞는 항을 인쇄하는 대신 79를 거부합니다

F(n) / F(n − 1)

비 출력입니다. 이것은 황금비가 아니고, 페이지도 그렇게 주장하지 않습니다. 다섯 번째 항에서 나오는 값은 1.66666667이고 1.618에서 멀리 떨어져 있습니다. 다만 빠르게 좋아지는 근삿값이며, 스무 번째 항이면 페이지가 인쇄하는 여덟 자리 안에서 이미 정확해집니다

φ = 1.6180339887…

이 비들이 수렴해 가는 수인 황금비입니다. x² = x + 1의 양의 해이며, 그 방정식은 같은 점화식을 방정식으로 다시 쓴 것입니다. 우연이 아니라, 피보나치의 비가 그 수에 내려앉는 이유입니다. 인쇄되는 근삿값은 기껏해야 1.61803399라는 점을 기억해 두십시오. 페이지는 여덟 자리를 보여 주고, 참값은 그 너머로 이어집니다

항을 확인하는 것이 가장 평범한 쓰임입니다. 퍼즐이 열 번째 피보나치 수를 묻거나 교과서의 수열이 손으로 더하기에 버거울 만큼 멀리 갈 때, 이 피보나치 계산기는 그 값과 거기까지 이르는 항의 나열을 함께 줍니다. 비 출력은 다른 질문에 답합니다. 황금비가 어디서 오는가 하는 질문입니다. 2, 1.5, 1.66666667, 1.6, 1.62500000, 1.61538462가 1.618로 가라앉는 것을 보는 편이 증명을 읽는 것보다 그 연결을 이해하는 훨씬 짧은 길이고, 이 페이지의 참고표는 바로 그렇게 읽도록 놓여 있습니다. 세 번째 쓰임은 프로그래밍과 수업에 있습니다. 이 점화식은 재귀의 첫 예제로, 이 수열은 재귀로 정의했지만 반복으로 계산하는 편이 훨씬 싼 예로 표준처럼 쓰입니다. 이 페이지의 루프가 반복판이고, 그래서 78항이 거의 공짜입니다. 이 수들은 스스로 불어나는 성장을 어림할 때도 나타납니다. 정사각형과 직사각형으로 띠를 채우는 방법의 수, 한 번에 한 칸이나 두 칸씩 오르는 계단의 경로 수, 해마다 갈라지는 식물의 가지 수가 모두 같은 점화식을 따릅니다. 질문이 수열이 아니라 그 비 자체에 관한 것이라면 golden-ratio-calculator가 그 수를 고유한 성질을 가진 하나의 수로 다루고, 성장 패턴에 관한 것이라면 exponential-growth-calculator가 이 항들이 계단처럼 근사하는 매끄러운 쪽을 다룹니다

1. 앞의 열 항: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

   1. 이 페이지가 쓰는 시작값 1과 1에서 출발합니다
   2. 1 + 1 = 2, 이어서 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8입니다
   3. 계속하면 5 + 8 = 13, 8 + 13 = 21, 13 + 21 = 34, 21 + 34 = 55입니다
   4. 열 항이므로 열 번째 항은 55이고, 마지막 두 항의 비는 55 ÷ 34 = 1.61764706입니다

   기본 입력입니다. 열 번째 항이 55이고 55와 34의 비가 1.61764706이라는 점을 보십시오. 황금비에 가깝지만 셋째 자리에서 아직 눈에 띄게 어긋나 있습니다. 그래서 이 수열은 조회할 가치가 아니라 지켜볼 가치가 있습니다. 수렴은 빠르지만 즉각적이지 않고, 열 항은 인쇄되는 여덟 자리가 1.61803399에 닿기에 아직 모자랍니다.

2. 가장 짧은 실행: 두 항

   1. 두 항은 이 페이지가 받아들이는 가장 작은 요청입니다
   2. 수열은 시작값 두 개 그대로이고 1과 1입니다
   3. 두 번째 항이 1이므로 제n항 출력은 1입니다
   4. 비는 1 ÷ 1 = 1이며, 이 페이지가 낼 수 있는 값 중 황금비에서 가장 먼 값입니다

   아래 끝이며, 그것이 1이 아니라 2인 이유입니다. 비 출력은 두 항이 있어야 존재할 수 있습니다. 항이 하나면 나눌 대상이 없으므로 페이지는 빈칸이나 0을 인쇄하는 대신 1을 거부합니다. 비가 1이라는 것은 이 수렴 전체의 출발점이기도 합니다. 그 뒤의 모든 비는 거기서 한 걸음씩 떨어진 값이고, 1에서 1.618까지 가는 여정을 아래 표가 항마다 펼쳐 놓았습니다.

3. 비가 자리를 잡는 곳: 스무 항

   1. 열 번째 항에서 점화식을 이어 갑니다. 34 + 55 = 89, 55 + 89 = 144이고 그 뒤로도 같습니다
   2. 스무 번째 항은 6765이고 열아홉 번째 항은 4181입니다
   3. 6765 ÷ 4181 = 1.61803396317…입니다
   4. 페이지가 인쇄하는 여덟 자리로 반올림하면 1.61803396입니다

   스무 항이면 충분합니다. 참 황금비는 1.6180339887로 시작하는데 여기의 근삿값은 일곱째 자리까지 그것과 일치하고, 어긋남은 인쇄되는 마지막 자리인 여덟째 자리에 남아 있습니다. 열 항일 때 오차가 이미 셋째 자리에서 보였던 것과 견주어 보십시오. 이 페이지가 존재하는 이유가 이 지점입니다. 이 점화식의 정의에는 황금비가 전혀 없는데도, 덧셈만으로 그것을 빠르게 만들어 냅니다.

항의 수는 2에서 78까지의 정수여야 합니다. 1은 비 출력이 두 항을 필요로 하기 때문에 거부하고, 79는 항들이 거기서부터 정확하지 않아지기 때문에 거부합니다. F(78)은 8944394323791464로 배정도 값에 정확히 들어가는 마지막 피보나치 수이고, F(79)는 9007199254740991이라는 상한을 넘어섭니다. 이 페이지는 근사한 항을 돌려주는 대신 요청을 거절합니다. 거의 맞지만 열여섯 자리로 인쇄된 수는 정확한 수와 똑같이 보이기 때문입니다. 번호는 1부터 세고, 이 페이지는 F(1) = F(2) = 1을 씁니다. 널리 퍼진 다른 관례는 F(0) = 0, F(1) = 1로 두어 모든 번호를 하나씩 밀어 버립니다. 그 관례에서는 다섯 번째 항이 5이고 여기서는 8입니다. 두 관례가 교과서에도 소프트웨어에도 쓰이므로, 다른 출처와 견주었을 때 값이 한 칸씩 어긋난다면 그것은 오류가 아니라 관례 차이입니다. 비 출력은 근삿값이고 여덟 자리로 인쇄됩니다. 유한한 항의 수에 대해 그것이 정확히 황금비가 되는 일은 없지만, 일흔여덟 번째쯤이면 인쇄되는 값과 황금비가 같은 여덟 자리가 됩니다. 항 자체는 쉼표로 구분된 목록으로 인쇄되고 천 단위 구분 기호를 쓰지 않으므로, 열 번째 항은 55로, 일흔여덟 번째 항은 8944394323791464로 읽힙니다. 긴 항을 소리 내어 읽는 일은 목록이 아니라 제n항 출력의 몫입니다. 마지막으로 아래 참고표는 앞의 열 항에 고정되어 있고 입력을 따라가지 않습니다. 입력한 값에 답하는 것이 아니라 비가 자리를 잡는 모양을 보여 주기 위한 표입니다.

수열은 F(0)에서 시작하나요, F(1)에서 시작하나요?

이 페이지는 F(1)에서 시작하므로 F(1) = 1, F(2) = 1, F(3) = 2이고 열 번째 항은 55입니다. 널리 쓰이는 다른 관례는 F(0) = 0, F(1) = 1로 두어 모든 번호를 하나씩 밀어 버립니다. 그 관례에서 다섯 번째 항은 5이고 여기서는 8입니다. 둘 다 교과서와 소프트웨어에서 쓰이고 어느 쪽도 오류가 아닙니다. 다만 다른 출처와 견주었을 때 값이 한 칸씩 어긋난다면 그 까닭이 이것입니다. 피보나치 답이 틀리는 가장 흔한 방식입니다.

비는 왜 곧바로 자리를 잡지 않고 계속 흔들리나요?

그것이 항등식이 아니라 극한이기 때문입니다. 각 항이 앞의 두 항을 더한 값이므로 이웃한 항의 비는 그 나름의 고정된 규칙에 따라 움직이고, 그 움직임은 목표값을 위아래로 번갈아 지나치면서 매번 폭이 절반쯤으로 줄어듭니다. 아래 표가 그것을 보여 줍니다. 2.00000000에서 1.50000000, 1.66666667, 1.60000000, 1.62500000으로 좁혀져 1.61538462와 1.61904762에 이릅니다. 열 항이면 가깝고, 스무 항이면 페이지가 인쇄하는 여덟 자리에 충분하며, 유한한 항으로 정확히 황금비가 되는 경우는 없습니다. 더 가까워질 뿐입니다.

황금비는 무엇이고, 이 수열이 그것을 왜 만들어 내나요?

황금비는 1.6180339887…이며 x² = x + 1의 양의 해입니다. 그 방정식은 피보나치의 점화식을 다르게 쓴 것이고, 비가 어떤 수에 자리를 잡는다면 그 수는 이 방정식을 만족할 수밖에 없습니다. 그래서 이 수열이 그 수에 내려앉고, 그래서 이 수렴이 우연이나 흥밋거리가 아닙니다. 이 수는 또 분수로 근사하기 가장 어려운 수입니다. 연분수가 전부 1이기 때문이고, 식물이 잎과 씨를 그 수로 벌려 놓는 것이 바로 그 성질을 이용하는 것입니다.

왜 78항까지만 요청할 수 있나요?

F(79)가 배정도 값이 정확히 담을 수 있는 가장 큰 정수인 9007199254740991보다 크기 때문입니다. F(78)은 8944394323791464로 정확하고, F(79)는 14472334024676221인데 이는 그 값에 가까운 다른 수로 저장됩니다. 페이지는 근삿값을 인쇄하는 대신 요청을 거부합니다. 열여섯 자리로 인쇄된 항은 정확한 항과 똑같이 보이고, 출력만 보고는 오차를 알아볼 방법이 없기 때문입니다. 이 상한은 수학의 사실이 아니라 부동소수점의 사실입니다. 수열 자체는 끝없이 이어집니다.

토끼 번식 문제는 어디서 나오나요?

피보나치는 이 수열을 퍼즐과 함께 소개했습니다. 한 쌍의 토끼로 시작해, 각 쌍이 성숙하는 데 한 달이 걸리고 그 뒤로 매달 새 쌍을 낳는다고 하고, 달마다 초의 쌍 수를 세는 것입니다. 그 수가 1, 1, 2, 3, 5, 8로 나옵니다. 지난달의 성숙한 쌍은 모두 살아 있고 이번 달의 새 쌍은 한 달 전에 성숙한 쌍에서 나오기 때문이며, 이것이 바로 그 점화식을 전혀 다른 방향에서 얻은 것입니다. 이 수열이 어느 한 응용으로 정의되는 것이 아니라는 것을 보여 주므로 알아 둘 만합니다.

앞의 항을 모두 나열하지 않고 제n항을 일반항으로 바로 구할 수 있나요?

원리상으로는 그렇고, 이 페이지의 제n항 출력이 그 수를 따로 한 줄로 보여 줍니다. 다만 그것은 지름길 공식이 아니라 같은 루프에서 나옵니다. 까닭은 정확도입니다. 황금비로 제n 피보나치 수를 곧바로 주는 닫힌 형식인 비네 공식이 있습니다만, 무리수를 거듭제곱하는 계산이라 부동소수점에서는 n이 커질수록 참 정수에서 멀어집니다. 정수를 더하는 쪽은 정확하고 그 공식은 그렇지 않습니다. 그래서 이 페이지는 더합니다. 시작값 두 개에서 앞으로 밀어 나가는 방식이 78항을 거의 공짜로 만드는 이유이기도 합니다. 풀 공식이 없고 덧셈이 76번 반복될 뿐입니다.

• Fibonacci Number — 점화식, 황금비로 쓴 닫힌 형식, 그리고 비가 그 수로 수렴하게 만드는 항등식 — Wolfram MathWorld (United States)
• Golden Ratio — 1.6180339887…이라는 수, x² = x + 1의 양의 근이라는 정의, 그리고 분수로 근사하기 가장 어려운 수인 이유 — Wolfram MathWorld (United States)
• Continued Fraction — 황금비의 연분수가 모두 1이라는 사실이 정확히 무엇 때문에 피보나치의 비를 그 수로 수렴시키는지 — Wolfram MathWorld (United States)
• 教育部关于印发义务教育课程方案和课程标准(2022年版)的通知 — 이 통지의 첨부 목록 제5항이 《义务教育数学课程标准(2022年版)》에 해당하며, 간단한 상황에서 변화 규칙을 탐구하는 것은 초등학교 수와 대수 영역의 내용이므로 원문과 학년군 요구는 이 첨부를 기준으로 합니다 — 中华人民共和国教育部