问题优化分析
已知K阶斐波那契数列序列定义为
试编写求k求k阶斐波那契数列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
分析：
显然各项值须依次递推的方式逐个求出, 每次计算，均只需前k个值。
关键：如何存储这k个值，当新的项计算出来后，存放在哪里。
辅助数据结构：int f[m]; 每个值都占用一个数组元素
STEP 1
step 1 长度为m的数组
如图，针对规模为m的问题，系统需要提供长度为m的数组；其中第i个元素的值由下标为[i-k: i-1]中的元素累加而来，且段落[0: i-k-1]的数组元素不参与计算，故可以将整个数组截短为长度为k的循环数组；
STEP 2
数组结构：
step 2 长度为k的数组
循环：
循环
新环状结构的数组的下标的计算：
这样我们将辅助空间的大小从m优化为了k。
STEP 3
从step2可知，下标为i的位置存放的元素f[i]是f[i-k:i-1]个元素的和，同理可知下标为f[i+1]的元素的和为f[i-k+1: i]的和；故可推知f[i+1]与f[i]的关系为
这样可以将辅助空间数组的大小从k进一步优化为3。
伪代码实现
int fibonacci(int m, int k ) {
if ( m < 0|| k<1 ) return -1; //约定-1表示参数错误
if ( m < k-1 ) return 0;
if ( m == k-1 || m == k ) return 1;
int f[k]; //存放“前k项”值
for( i = 0; i < k - 1; k++) f[i] = 0; //初始化数列前k项
f[k-1] = f[k] = 1;
for( i = k; i < m; i++) { //逐项计算数列值
v = 2 * f[i % k] – f[(i - k) % k]; //循环读取，计算第i+1项
f[(i+1)%k] = v; //循环存放
}//for
return v; //数列的第m项值
}//fibonacci
