0001 #include <ctime>
0002 #include <iostream>
0003 using namespace std;
0004 
0005 #include "Fib.h"
0006 
0007 uint64_t  fibI(int n); //迭代版
0008 constexpr uint32_t TABLE_SIZE = 256;
0009 uint64_t  M[TABLE_SIZE]; //快查表
0010 uint64_t  fibM(int n); //记忆化版
0011 uint64_t  fib(int n); //二分递归版
0012 uint64_t  fibL(int n, uint64_t& f); //线性递归版
0013 
0014 int main(int argc, char* argv[]) { //测试FIB
0015 //检查参数
0016    if (2 > argc) { fprintf(stderr, "Usage: %s <Rank>\n", argv[0]); return 1; }
0017    int n = atoi(argv[1]);
0018 //依次计算Fibonacci数列各项
0019    printf("\n------------- class Fib -------------\n");
0020    Fib f(0);
0021    for (int i = 0; i < n; i++, f.next())
0022       printf("fib(%2d) = %22I64d\n", i, f.get());
0023    for (int i = 0; i <= n; i++, f.prev())
0024       printf("fib(%2d) = %22I64d\n", n-i, f.get());
0025    printf("\n------------- Iteration -------------\n");
0026    for (int i = 0; i < n; i++)
0027       printf("fib(%2d) = %22I64d\n", i, fibI(i));
0028    printf("\n------------- Linear Recursion -------------\n");
0029    for (int i = 0; i < n; i++) {
0030       uint64_t f;
0031       printf("fib(%2d) = %22I64d\n", i, fibL(i, f));
0032    }
0033    printf("\n------------- Memoization -------------\n");
0034    memset(M, 0xFF, sizeof(uint64_t)*TABLE_SIZE);
0035    M[0] = 0; M[1] = 1;
0036    for (int i = 0; i < n; i++)
0037       printf("fib(%2d) = %22I64d\n", i, fibM(i));
0038    printf("\n------------- Binary Recursion -------------\n");
0039    for (int i = 0; i < n; i++)
0040       printf("fib(%2d) = %22I64d\n", i, fib(i));
0041    return 0;
0042 }