C语言：求第N个斐波那契数

斐波那契数：
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？

我们不妨拿新出生的一对小兔子分析一下：

第一个月小兔子没有繁殖能力，所以还是一对；

两个月后，生下一对小兔总数共有两对；

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；

……

依次类推可以列出下表：

经过月数 0 1 2 3 4 5 6 7 8 9 10 11 12
幼仔对数 1 0 1 1 2 3 5 8 13 21 34 55 89
成兔对数 0 1 1 2 3 5 8 13 21 34 55 89 144
总体对数 1 1 2 3 5 8 13 21 34 55 89 144 233
表中数字1，1，2，3，5，8－－－构成了一个序列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。这个数列是意大利中世纪数学家斐波那契在《算盘书》中提出的，这个级数的通项公式，除了具有an+2=an+an+1的性质外，还可以证明通项公式为：an=1/√5[（1/2+√5/2）^n-（1/2-√5/2）^n](n=1,2,3…..）（√5表示根号5）

这个通项公式中虽然所有的an都是正整数，可是它们却是由一

些无理数表示出来的。

即在较高的序列，两个连续的“斐波纳契数”的序列相互分割

将接近黄金比例（1.618:1或1:0.618）。

例如：233/144，987/610、、、、

斐波那契数列还有两个有趣的性质

⒈斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1;

⒉任取相邻的四个斐波那契数，中间两数之积（内积）与两边两数之积（外积）相差1.

同样我们还可以有t阶斐波那契数列，通过递推数列a(n+t)=a(n+t-1）+a(n+t-2）+…+a(n），其中a⑴=a⑵=1，以及对于3-t<=n<=0，有a(n)=0.

给出了t阶斐波那契数列的通项公式：

[r^(n-1）（r-1）/((t+1）r-2t)]，其中r是方程x^{t+1}-2x^t+1=0的唯一一个大于1的正数根（可以看出r非常接近2）

#define _CRT_SECURE_NO_WARNINGS 10
#include
#include

long long fib(int num)
{
    if (num <= 2)
    {
        return 1;
    }
    return fib(num-1)+fib(num-2);
}

int main()
{
    int num = 0;
    printf("请输入一个数：");
    scanf("%d", &num);
    printf("%d \n", fib(num));
    system("pause");
    return 0;
}

/*long long fib(int num)
{
    long long prev = 1;
    long long pprev = 1;
    long long date = 1;
    while (num>2)
    {
        date = prev + pprev;
        pprev = prev;
        prev = date;
        num--;
    }
    return date;
}

int main()
{
    int num = 0;
    printf("请输入一个数：");
    scanf("%d", &num);
    printf("%d \n", fib(num));
    system("pause");
    return 0;
}*/