[C] 피보나치 수열(Fibonacci sequence)

피보나치 수열(Fibonacci sequence)이란 첫 번째 항이 0, 두 번째 항이 1, 세 번째 항부터는 그 앞의 두개의 수를 더한 값을 갖는 수열을 말한다.

즉 {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,,,} 과 같이 나열되는 수열이다.

 

이번에 만들어 볼 프로그램은 사용자로부터 원하는 숫자를 입력받고, 그 입력받은 숫자에 해당하는 자리에 있는 피보나치 수열 항의 값을 찾아 출력해주는 프로그램이다.

 

출력 예시는 다음과 같다.

숫자를 입력하시오 : 7
7번째 피보나치 수열은 8입니다.

 

Fibonacci라는 함수를 선언하여 만들 것이다.

 

그 구조는 아래와 같다.

#include <stdio.h>

int Fibonacci(int n)
{ 
  if (n==1) return 0;
  if (n==2) return 1;
  if (n==3) return 1;
  
  int a = 0, b = 1, c = 1;

  for(int i=0; i<n-3; i++) {
    a = b;
    b = c;
    c = a + b;
  }
  return c;
}

int main()
{
  int num;
  printf("숫자를 입력하시오 : ");
  scanf("%d", &num);
  printf("%d번째 피보나치 수열은 %d입니다.\n", num, Fibonacci(num)); 

  return 0;
}