## Find the kth order Fibonacci numbers

1. Define the problem:

**Formal Definition:**

*F*=^{(k)}_{n}*F*+^{(k)}_{n-1}*F*+ . . . +^{(k)}_{n-2}*F*for n ≥ k.^{(k)}_{n-k}*F*= 1^{(k)}_{k-1}*F*= 0 for 0 ≤ n ≤ k-2^{(k)}_{n}

Q: Get the kth order F(m)

2. Examples:

（1）k = 1

f(0) = 1,f(1) = 1;……..f(m) = 1;

(2) k = 2

f(0) = 0,f(1) = 1; f(2) = 1;f(3) = 2; f(4) = 3;f(5) = 5;

(3) k = 3

f(0) = 0,f(1) = 0; f(2) = 1;f(3) = 1; f(4) = 2;f(5) = 4;f(6) = 7;

3. Methods:

f(m) = f(m-1)+f(m-2)+f(m-3)+……+f(m-k)—————-(1)

f(m-1) = f(m-2)+f(m-3)+f(m-4)+……+f(m-k-1) ———-(2)

From (1) – (2), get:

f(m)-f(m-1) = f(m-1)-f(m-k-1)

so f(m) = 2*f(m-1)-f(m-k-1)

4. Algorithms:

A. recursion:

#include <iostream> using namespace std; int fbi (int k, int m) { if(m==k-1||m==k) return 1; if(m<k-1) return 0; return 2*fbi(k,m-1)-fbi(k,m-k-1); } int main () { int z; z = fbi (6,9); cout << "The result is " << z; cin.get(); return 0; }

Code Complexity O(k^m), if store the middle value, we get O(m^2)

B.Array

</pre> #include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define MAX_M 100 typedef int Status; Status fib(int k,int m,int &f) { int temp[MAX_M]; if(k<2||m<0) return ERROR; if(m<k-1) f=0; else if (m==k-1 || m==k) f=1; else { for(int i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1;temp[k]=1; for(int i=k+1;i<=m;i++) temp[i]=2*temp[i-1]-temp[i-k-1]; f=temp[m]; } return OK; } int main () { int z; fib (2,5,z); cout << "The result is " << z; cin.get(); return 0; }

Code Complexity: O(m), Storage O(temp.size)