Posts Tagged ‘ code ’

Find the kth order Fibonacci numbers

1. Define the problem:

Formal Definition:

  • F(k)n = F(k)n-1 + F(k)n-2 + . . . + F(k)n-k      for n ≥ k.
  • F(k)k-1 = 1
  • F(k)n = 0      for   0 ≤ n ≤ k-2

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>
&nbsp;

#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)

Advertisements