[C언어/알고리즘] n번째 피보나치 수 출력하기

숫자 n을 입력받고 n번째 피보나치 수를 출력하는 문제다.
피보나치 수열이란 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.
다음 피보나치 수열을 보자.

0 1 1 2 3 5 8 13 21 34 55 89 144 ......n

1번째 항은 0과 1이고,
3번째 항 = 1번째 항 + 2번째 항
4번째 항 = 2번째 항 + 3번째 항
5번째 항 = 3번째 항 + 4번째 항
...
...
으로 이루어져 있는 것을 확인할 수 있다.

만약 7을 입력하면 피보나치 수열에서 7번째에 위치한 8이 출력되고,
11을 입력하면 55가 출력되어야 한다.

 

입력예시]

입력 : 15

 

출력예시]

15번째 항의 피보나치 수 = 377

 

아래 코드 외에 재귀함수로 구현하는 코드도 있습니다. 성능은 안 좋습니다.

 

 

_M#]