[Hermeneutics] 2. 피보나치 수열

피보나치 수열

 

2009. 10. 06 (月)

 

 

  갓 태어난 토종 진돗개 암수 한 쌍을 선물 받았다. 이걸 가지고 사업을 해보려고 한다. 이 진돗개는 태어나서 2개월이 지나면 성장해서 어미가 되고 그 후 매월 암수 한 쌍씩의 새끼를 낳는다고 할 때 21개월 후에는 모두 몇 쌍의 진돗개가 될까? 단 진돗개는 불로초를 먹여 절대 죽지 않는다.

 

Ø  요구사항

-       재귀 함수를 사용해서 나타낼 것

-       재귀 함수를 사용하지 않고 나타낼 것

-       재귀 함수가 총 몇 번 호출 되었는지 나타낼 것

-       Int 형으로 하였을 땐 일정 수치가 넘으면 엉뚱한 값으로 컴퓨터 한계 수치를 안다.

-       재귀형과 일반형 템플릿 형으로 CPU 점유율을 안다.

-       Static 변수의 사용을 안다.

 

Ø  Tip

-       첫 항이 1 그리고 둘째 항이 1 이면서 그 다음은 두 수를 점점 더해가면서 생성된다.

-       점화식은

-       재귀 호출의 횟수는 static 변수를 이용하여 나타낸다.

-       피보나치 수열의 일반항은 다음과 같다

 

  

 

 

#include <stdio.h> #include <math.h> #include <stdlib.h> #define SIZEERROR 1 #define VALUEERROR 2 void ErrorMsg(int nData); double Fivonachi(double nCount); void main() {        double nInputData, nData;        printf("피보나치수열\n");        scanf("%lf", &nInputData);        if(nInputData < 1.0)        {              ErrorMsg(SIZEERROR);              exit(EXIT_FAILURE);        }        if(modf(nInputData, &nData) != 0.0)        {              ErrorMsg(VALUEERROR);              exit(EXIT_FAILURE);        }        nData = Fivonachi(nInputData);        printf("%lf", nData); } double Fivonachi(double nCount) {        if((nCount == 1.0) || (nCount == 2.0))        {              return 1.0;        }        else        {              return Fivonachi(nCount-1.0) + Fivonachi(nCount-2.0);        } } void ErrorMsg(int nData) {        switch(nData)        {              case SIZEERROR:                     printf("1보다큰수로설정해야함\n");              break;                case VALUEERROR:                     printf("정수로설정해야함\n");              break;                default:              break;        } }