Question

数据结构02 - 斐波那契(Fibonacci)数列问题分析

Answer 1

已知K阶斐波那契数列序列定义为

试编写求k求k阶斐波那契数列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

分析：
显然各项值须依次递推的方式逐个求出, 每次计算，均只需前k个值。
关键：如何存储这k个值，当新的项计算出来后，存放在哪里。
辅助数据结构：int f[m]; 每个值都占用一个数组元素

STEP 1

如图，针对规模为m的问题，系统需要提供长度为m的数组；其中第i个元素的值由下标为[i-k: i-1]中的元素累加而来，且段落[0: i-k-1]的数组元素不参与计算，故可以将整个数组截短为长度为k的循环数组；

STEP 2

数组结构：

循环 ：

新环状结构的数组的下标的计算：

这样我们将辅助空间的大小从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。