The Fibonacci sequence
The Fibonacci sequence is one that comes up a lot.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
One definition for the sequence is the numbers 1 and 1 and then the next number is the sum of the two previous numbers and so on. So, if the 1st and 2nd Fibonacci numbers are both 1 then the 3rd is 1st + 2nd (2), and the 4th is the 3rd + 2nd (3).
fib 1 = 1 fib 2 = 1 fib n = fib (n-1) + fib (n-2)
The hard coded ones for the first two numbers look ripe for some parametrisation.
Write a Fibonacci like sequence generator that can be parametrised on the first two numbers
If you play around with this program you will find that if you start with the numbers 0 and 1 you will from then on get the same Fibonacci sequence as above.
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
This has the effect of prefixing the Fibonacci sequence with a zero and could be counted as the zeroth number in the sequence.
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
You should be able to continue to use your program to work out the next prefix, that is the next number that you can add to the start of the sequence and still generate the same sequence.
When you have this number we can see that it is what the result of fib -1 should be.
Continue to work out more prefix numbers. You should be able to work out the values for fib -2, fib -3, fib -4 etc.
Although you can look up the answer to this it'll be more interesting to try to use your program to experiment. With the language you have used is it possible to easily experiment — i.e. can you do this interactively, or do you have to go through a compile sequence each time you want to try out a new number? Maybe you've written an interface that allows you to experiment easily?
Write a new Fibonacci function that generalises the sequence you've found so that it can be called with any positive or negative integer.
Bring your programs with you to BeerCamp on Wednesday (venue to be confirmed — but it'll be announced on the BarCamp Thailand Google group), describe them on your blog or just post here. It would be really interesting to hear how you've gone about solving the problems rather than just posting a solution.
(To post code here prefix each line with four spaces. You will need to make sure you avoid Mediawiki syntax in the code itself. Watch out especially for [ and ] which are used for links, and doubled up single apostrophes.)
Discussion for this page
