斐波拉契数列的第n项

1
2
3
4
5
6
7
8

long fab1(int n)
{
    if (n < 3)
    {
        return 1;
    }
    return fab1(n - 2) + fab1(n - 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

long fab2(int n)
{
    long nums[n];
    nums[0] = 1;
    nums[1] = 1;
    for (int i = 2; i < n; i++)
    {
        nums[i] = nums[i - 2] + nums[i - 1];
    }
    return nums[n - 1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

long fab3(int n)
{
    long first = 1;
    long second = 1;
    long current = 1;
    for (int i = 3; i <= n; i++)
    {
        current = first + second;
        first = second;
        second = current;
    }
    return current;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
#include <ctime>

using namespace std;

void fun_cost(long (*func)(int), int n)
{
    time_t begin, end;
    time(&begin);
    long result = (*func)(n);
    time(&end);
    double difference = difftime(end, begin);

    const char *format = "n: %d result: %ld cost: %f";
    int len = snprintf(NULL, 0, format, n, result, difference);
    char *s = (char *)malloc(len + 1);
    sprintf(s, format, n, result, difference);
    std::cout << s << endl;
}

int main()
{
    fun_cost(fab1, 45);
    fun_cost(fab2, 45);
    fun_cost(fab3, 45);
    return 0;
}