​斐波那契数列算法中究竟应该使用哪种数据类型呢？

总结

• unsigned long long，能表示的最大斐波那契数是第119个；

• long long，能表示的最大斐波那契数是第92个；

• double，long long，能表示的最大斐波那契数是第1476个；

so，貌似使用哪种类型都不合适，兔子数列增长太快了。

▼▼▼▼▼▼▼▼▼

NO.01 unsined long long类型

能表示的最大斐波那契数是第119个

代码如下：

#include<bits/stdc++.h>
using namespace std;
unsigned long long number(int n);

int main(void)
{
    int num;
    printf("你要计算第几个数？(q to quit):\n");
    while(scanf("%d", &num) ==1)
    {
        if(num <0)
            printf("无效的数字\n");
        else
        {
            printf("第%d 个数是\n%llu\n", num, number(num));
        }

        printf("unsigned long long 可以表示的最大的数为\n%llu\n", ULLONG_MAX);
    }
    return 0;
}

unsigned long long number(int n)
{
    unsigned long long x1 =0, x2 =1, xn =0;
    if(n <3)
        xn =1;
    else
    {
        for(int i =2; i <= n; ++i)
        {
            xn = x1 + x2;
            x1 = x2;
            x2 = xn;
        }
    }

    return xn;
}

输出如下

斐波那契数ull.png

▼▼▼▼▼▼▼▼▼

NO.02 long long类型

能表示的最大斐波那契数是第92个

#include<bits/stdc++.h>
using namespace std;
long long number(int n);

int main(void)
{
    int num;
    printf("你要计算第几个数？(q to quit):\n");
    while(scanf("%d", &num) ==1)
    {
        if(num <0)
            printf("无效的数字\n");
        else
        {
            printf("第%d 个数是\n%lld\n", num, number(num));
        }
        printf("long long 可以表示的最大的数为\n%lld\n", LLONG_MAX);
    }
    return 0;
}

long long number(int n)
{
    long long x1 =0, x2 =1, xn =0;
    if(n <3)
        xn =1;
    else
    {
        for(int i =2; i <= n; ++i)
        {
            xn = x1 + x2;
            x1 = x2;
            x2 = xn;
        }
    }
    return xn;
}

斐波那契数ll.png

▼▼▼▼▼▼▼▼▼

NO.03 double 类型

能表示的最大斐波那契数是第1476个

#include <bits/stdc++.h>
using namespace std;

double number(int n);
int main(void)
{
    int num;

    printf("你要计算第几个数？(q to quit):\n");
    while (scanf("%d", &num) == 1)
    {
        if (num < 0)
            printf("无效的数字\n");
        else
        {
            //printf("第%d 个数是\n%lld\n", num, number(num));
            cout<<num<<"--"<< number(num)<<endl;
        }

        //printf("long long 可以表示的最大的数为\n%lld\n", LLONG_MAX);
    }
    return 0;
}

double number(int n)
{
    double  x1 = 0, x2 = 1, xn = 0;
    if (n < 3)
        xn = 1;
    else
    {
        for (int i = 2; i <= n; ++i)
        { 
            xn = x1 + x2;
            x1 = x2;
            x2 = xn;
        }
    }

  return xn;
}

斐波那契数double.png