题目
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
