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)

What the new trending of my knowledge technology

So as the first kind like a showing all my mistake English blog, I will do a apologize first to who look at this blog. The way the technology working is related to different people. So please begin with a first question in your mind: What’s the future technology will be? Don’t pre-insert some other people’s idea in your mind. Leave those stuffs just out of your mind for a moment. I am not questioning those stuff but some of them may be a tool for advertising or over advertised power.

Suppose you have a answer already, that’s good. Then I will share with you some of my knowledge of the technology.

First, Interaction. This interaction is not only the input way to the devices we have but also including output. Think about why iphone is so popular at the beginning. That’s really a interaction promoted industry line — touching mobile, tablet and laptop even desktop. That’s a idea to create or combine them to some level of other stuffs. Here the stuffs can be anything: your window, your table, your cup, your watch, your car, you name it. Just give you an example how this works. The other I need to mention is Augment Reality. Don’t be afraid by this term too much. Think it easily and with a lot of fun (the reason is that the accurate need us to be a fun stuff right now). But that’s fine it’s OK to start some simple business here. Not using some fancy tools but your owned devices: any IOS, Android can be used here right now. Think about it when you move your phone to some stuff (may be a QR code, a lot of use now) you can view a virtual ball in you cell phone and by clicking it it will pop up something(a website or a dynamic tool created). That’s it who knows how we can use this technology to but we all know simple step makes it becoming more powerful.

加关注

每发布一篇新博文的同时向您的邮箱发送备份。