题目

Super Fibonacci数列的通项如下：
F0 = F1 = F2 = F3 = F4 = 1
Fn = 2018 * Fn-1 + 2017 * Fn-2 + 2016 * Fn-3 + 2015 * Fn-4 + 2014 * Fn-5
输入描述:
有多组测试数据，每组数据输入n，表示待求的第n个Super Fibonacci数列
对于每个输入n，满足1 <= n <= 4611686018427387904
输出描述:
输出第n个Super Fibonacci数列值模1000000003的值
编程语言：python27

解法1：递归版

写个记忆体

import sys
Fib = {0:1, 1:1, 2:1, 3:1, 4:1}
def Super_fib(n):
    if n in Fib:
        return Fib[n]
    else:
        tmp = 2018*Super_fib(n-1) + 2017*Super_fib(n-2) + 2016*Super_fib(n-3) + 2015*Super_fib(n-4) + 2014 * Super_fib(n-5)
        Fib[n] = tmp
        return tmp 
print Super_fib(1002) % 1000000003

n最大可到1002（python3默认最大递归次数998）

869327306
[Finished in 0.0s]

调整递归最大次数

import sys
sys.setrecursionlimit(200000) #设置最大递归次数200000

Fib = {0:1, 1:1, 2:1, 3:1, 4:1}
def Super_fib(n):
    if n in Fib:
        return Fib[n]
    else:
        tmp = 2018*Super_fib(n-1) + 2017*Super_fib(n-2) + 2016*Super_fib(n-3) + 2015*Super_fib(n-4) + 2014 * Super_fib(n-5)
        Fib[n] = tmp
        return tmp 
print Super_fib(14977) % 1000000003

结果测试最大递归次数为14977

413656735
[Finished in 0.6s]

再增大 ex. n=14978, 其实此时应该是递归深度过大导致堆栈空间用尽。

https://answers.ros.org/question/238081/python-process-died-exit-code-11/
-11 is a SEGFAULT. For a Python interpreter, that is a bit of a strange error to run in to.

[Finished in 0.1s with exit code -11]

解法2：迭代版

上述改成迭代版, 从5的指数级运算降到线性级
关于defaultdict, 参考 https://www.jianshu.com/p/8cd027111930

import sys
from collections import defaultdict
Fib = defaultdict(int)
# Fib = {}
Fib[0] = 1
Fib[1] = 1
Fib[2] = 1
Fib[3] = 1
Fib[4] = 1
n = 100000
for _n in xrange(5,n+1):
    # print _n
    Fib[_n] = 2018*Fib[_n-1] + 2017*Fib[_n-2] + 2016*Fib[_n-3] + 2015*Fib[_n-4] + 2014 * Fib[_n-5]
print Fib[_n] % 1000000003

测试N=100000,平均耗时49.5s

# n  = 100000, try1
494062125
[Finished in 48.0s]
# n  = 100000, try2
494062125
[Finished in 51.0s]

解法3

在解法2基础上改进，以便减少缓存
加上一句'del Fib[_n-5]'，减杀动态缓存占用空间：原理每次迭代是删除_n-5，结果是整个缓存只保留n~n-4项：

# 以N=200000举例
defaultdict(<type 'int'>, {200000: xxx, 199996: xxx, 199997: xxx, 199998: xxx, 199999: xxx})

代码：

import sys
from math import log
from collections import defaultdict
Fib = defaultdict(int)
# Fib = {}
Fib[0] = 1
Fib[1] = 1
Fib[2] = 1
Fib[3] = 1
Fib[4] = 1
n = 100000
for _n in xrange(5,n+1):
    # print _n
    Fib[_n] = 2018*Fib[_n-1] + 2017*Fib[_n-2] + 2016*Fib[_n-3] + 2015*Fib[_n-4] + 2014 * Fib[_n-5]
    del Fib[_n-5]
print Fib[_n] % 1000000003

同样取n=100000,运行时间从49.5s降至17.2s

494062125
[Finished in 17.2s]

解法4:

参考：
台阶问题：斐波那契数列的扩展问题研究
第二节 常系数线性齐次递推关系_百度文库

举例详解.png

解重根时

多重特征根解.png

解法5：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// copy fib[4-1] to fib[3-0]
unsigned long * copy(unsigned long _Fib[]){
    for (int i = 1; i <= 4; ++i)
    {
        /* code */
        _Fib[i-1] = _Fib[i];
    }
    return _Fib;
}
unsigned long Fib(unsigned long n, unsigned long _Fib[]){
    printf("Fib start,the n value is %lu \n",n );
    unsigned long tmp;
    unsigned long _n = n - 4; //judge that if n >= 5
    unsigned long test = 0;
    unsigned long T = 0;
    unsigned long start, end;
    if (_n>0)
    {
        /* code */
        for (int i = 0; i < _n; ++i)
        {
            tmp = 2018*_Fib[4] + 2017*_Fib[3] + 2016*_Fib[2] + 2015*_Fib[1] + 2014*_Fib[0];
            _Fib = copy(_Fib);
            _Fib[4] = tmp % 1000000003;
            // // test if the _Fib[] repeeat period
            // if (test == 0)
            // {
            //     /* code */
            //     test = _Fib[4];
            //     start = i;
            // }
            // else{
            //     if (test == _Fib[4])
            //     {
            //         /* code */
            //         end = i;
            //         T = end - start;
            //         break;
            //     }
            // }
        }
    }
    // print the value of T 
    // printf("the T value is %lu\n",T );
    // print the value
    printf("the tmp value is %lu\n", tmp);
    printf("the _Fib[] value is:\n");
    for (int i = 0; i < 5; ++i)
    {
            /* code */
        printf("%lu,",_Fib[i] );
    }
    return _Fib[4];
}

int main(){
    unsigned long n;
    n = 4294967295;
    // n = 1112851462;
    // n = 8;
    // unsigned long n = 4611686018427387904;  //19 bits
    // int n = 300000000;
    // int n = 50;
    unsigned long _Fib[5] = {1,1,1,1,1};
    // scanf("input");
    printf("\ntest start:\n");
    // test run time
    clock_t begin,end;
    // start to log time
    begin = clock();
    unsigned long mod;
    mod = Fib(n, _Fib);
    // end time
    end = clock();
    double cost = (double)(end - begin)/CLOCKS_PER_SEC;
    // Fib(n);
    printf("the running time is %lf secs\n", cost);
    printf("mod value:\n%lu\n\n", mod);
    return 0;   
}

运行N=4294967295，32.75S。

image.png