[C언어] 피보나치 수열

예전에 주변의 것들을 하나하나 C언어로 표현하는 실험을 많이 했었는데 생각나는 것 중에 하나를 선택하여 코딩을 해던 것을 post로 작성 합니다.

1. 피보나치 수열

피보나치 수란 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다고 정의를 내릴 수 있습니다.

이 피보나치 수열을 수식으로 표현하면 아래와 같습니다.

[공식]

참고로, 위 공식은 0번째부터 시작 합니다. 만약 n=10이면 위치는 11번째가 되니깐 혼동하시면 안됩니다.

n=10이면,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

55가 됩니다.

55가 나오는지 코딩을 해 볼까요.

2. 코딩

위 공식을 재귀문을 이용하여 그대로 코딩을 하면 다음과 같습니다.

int Fibonacci(int n)
{
   if(n==0) return 0;
   if(n==1) return 1;
   return ( Fibonacci(n-1) + Fibonacci(n-2) );
}

피보나치수열 재귀문 코딩이 복잡하지 않죠.

종합해보면,

#include 

int Fibonacci(int n)
{
   if(n==0)
      return 0;
   if(n==1)
      return 1;
   return ( Fibonacci(n-1) + Fibonacci(n-2) );
}
 
void main()
{
   int n, val;
   printf("피보나치 수열\n");
   printf("n = ");
   scanf("%d",&n);
   printf("%d\n",n);
     
   val=Fibonacci (n);
   printf("결과 : %d\n",val);
   return 0;
}