Fibonacci number is defined simply by the following equations:
y(1) = 1
y(2) = 1
y(k) = y(k-1)+y(k-2) for all k > 2
Hence we will have a sequence like this: 1, 1, 2, 3, 5, 8, 13,... ad infinitum
The Challenge
To code a complete program fib(n) that will generate the first n-th Fibonacci number as compact as possible on the source code level. This is in contrary with the the common code optimization which depend a lot on the hardware and compiler. What I am striving to do here is to accomplish this task with the minimum number of statements.
But first question you, my dear reader may ask is "What is this for?". Answer: nothing, just for the hack of it due to boredom. Subsequent question could be "This is not fair to compare language X against language Y because X is for some A purpose and Y is for some B purpose, etc.", well, I will do this in a way as fair as I could make it, but in the real programming world, you seldom get the tool which is truly apt for the problem in hand. Don't believe me? Join a large company and see.
Any language can be used, including assembly language (bless you though).
You may assume the input parameter n is a positive integer > 2 (to avoid the corner cases) and is always valid and sane.
To kick start this, let's have our first foray in C.
To compile: 'gcc -o fib fib.c'.
#include <>
int main()
{
int i = 0;
for(i=1; i<10; i++)
printf("Fib %d is %d\n", i, fib(i));
return 0;
}/* main */
int fib (int n)
{
if (n <= 2) return 1;
else return fib(n-1) + fib(n-2);
}/* fib */
3 comments:
Have you tried using a very, very large number for your loop? Say INT_MAX?
My implementation isn't efficient, as for each number n, it recalculates all previous numbers. So under Cygwin, the calculation is basically stopped at n=45. That is an interesting question on how to balance aesthetic beauty of the code and practicality of implementation. No, not claiming my current implementation is beautiful though, just a generalized comment from there on.
Post a Comment