2. 피보나치 수열

https://www.youtube.com/watch?v=WpzjpKt0lbc&list=PLVoihNyHW4xkm_KJ8_N8X7F6EQP4uSRyR&index=3 

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

 

피보나치 수 

는 다음과 같은 초기값 및 점화식으로 정의되는 수열이다.F_{1}=F_{2}=1

 F_{n}=F_{n-1}+F_{n-2}

0번째 항부터 시작할 경우 다음과 같이 정의된다.

 F_{0}=0

 F_{1}=1

 F_{n}=F_{n-1}+F_{n-2}

피보나치 수의 처음 몇 항은 (0번째 항부터 시작할 경우) 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ... (OEIS의 수열 A000045)

수열 - 위키백과, 우리 모두의 백과사전

 

문제 소개

- 피보나치 수열을 출력해라

- An = An - 1 + An - 2

- 1 1 2 3 5 8 13 21 34 -------

- 수 하나를 입력 받아서 그 수에 해당하는 피보나치 수열 출력하기

-ex) 4를 입력하면 5 출력하기!!

<출력>