알고리즘 편-피보나치 수열 N항의 다양한 해결 방식: 귀속, 비귀속, 미귀속

  1
  2  ： * 。
  3 
  4  ： * 。
  5 
  6 //fib 
  7 
  8 
  9 #include<stdio.h>
 10 
 11 //       
 12 int  fib_1(int n)
 13 {
 14     if (n<3)
 15         return 1;
 16 
 17     else
 18         return fib(n-1)+fib(n-2);
 19 
 20 
 21 
 22 
 23     }
 24 
 25 // 
 26 int fib_2(int n )
 27 {
 28     int first=1;
 29     int second=1;
 30     if(n<3)
 31         return 1;
 32     else
 33      {
 34          int i=n;
 35          for(;i>2;--i)
 36         {
 37          int tmp=first;
 39          first=second;
 40          second=tmp+second;
 41          }
 42          return second;
 43     }
 44 
 45 
 46     }
 47 
 48 
 49 
 50 // ：first second 1；
 51 int fib_3(int first,int second,int n)
 52 {
 53 
 54     if(n<3)
 55     return 1;
 56 
 57     if(n==3)
 58     return first+second;
 59  
 60     first=second; 
 62     second=first+second;
 63     return fib_3(first,second,n-1);
 64    }

테스트 용례:

int main()
{
  int ret_1=fib_1(5);
  int ret_2=fib_2(5);
  int ret_3=fib_3(1,1,5);

  printf("%d  ",ret_1);
  printf("%d  ",ret_1);
  printf("%d  ",ret_1);
  return 0;
}