有关斐波那契数列的算法

斐波那契数列：1、1、2、3、5、8、13、21、…… 
　　如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式： 
　　F(0) = 0，F(1)=1，F(n)=F(n-1)+F(n-2) (n≥2)， 
　　显然这是一个递推数列。 

这里就不推导了。我们只是分析碰到一些类似问题时要灵活的应用这个数列。

最早引入这种数列的是兔子问题，后续有还有奶牛的问题，只不过是间隔不一样，
兔子的间隔是2，奶牛的间隔是3（f(n) = f(n-1) + f(n-3)）;
斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数、黄金矩形、黄金分割、等角螺线等，有时也可能是我们对斐波那契额数过于热衷，把原来只是巧合的东西强行划分为斐波那契数。比如钢琴上白键的8，黑键上的5都是斐波那契数
下面是自己写的关于奶牛的两种实现， 效率真不是一般的差距；

void
time_cur_print(void)
{
    time_t cur_time;
    struct tm *time_info;

    time(&cur_time);
    time_info = localtime(&cur_time);
    printf("%s\n", asctime(time_info));
    return;
}

unsigned long long
recursion_cow(int n)
{
    if(n <= 0)
        return ;

    switch(n)
    {
        case 1: return 1; break;
        case 2: return 1; break;
        case 3: return 1; break;
        default:
                return recursion_cow(n-1) + recursion_cow(n-3);

    }
}

int
no_recursion_cow(int n, unsigned long long *num)
{
    unsigned long long cow[3] = {1,1,1};
    int index;
    unsigned long long tmp3;

    if(n <= 3)
        return *num;

    for(index = 4; index <= n; index++)
    {
        tmp3 = cow[0] + cow[2];
        cow[0] = cow[1];
        cow[1] = cow[2];
        cow[2] = tmp3;
    }


    *num = tmp3;

    return tmp3;
}

int
main(void)
{
    int n;
    unsigned long long num;

    num = 1;

    printf("pls enter the year and cow : \n");
    scanf("%d", &n);

    printf("after %d years:\n", n);



    time_cur_print();
    no_recursion_cow(n, &num);
    time_cur_print();
    printf("no_recursion_cow : %llu\n", num);

    time_cur_print();
    printf("recursion_cow :  %llu\n", recursion_cow(n));
    time_cur_print();

    return 0;
}

希望自己以后碰到可以触类旁通。