I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Fibonacci Sequences

07.25.2012
| 4763 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Generate the nth Fibonacci Number

Today we'll tackle another classic CS problem, the Fibonacci sequence. The first two numbers in the sequence are 0 and 1, and each subsequent number is the sum of the previous two. So, it looks like

0,1,1,2,3,5,8,13,21 ......

What you have to do is provide a function that takes a parameter n that returns the Fibonacci number at the nth position.  

Catch up on all our previous puzzlers here

Comments

Vijay Nathani replied on Thu, 2012/07/26 - 1:49am

Groovy solution. As a sample, first 8 numbers are printed.

def fibonacci( int n) {
	def lastSum = BigInteger.ZERO
	(n <= 1)? lastSum : (2..n).inject(BigInteger.ONE) { sum,sequence ->  def o = lastSum; (lastSum = sum).add(o) }
}
(1..8).each { println fibonacci(it) }

 

Straub Edwin replied on Thu, 2012/07/26 - 4:52am

Java recursive solution: 
int fib(int n) {
    if (n == 1) {
      return 1;
    } else if (n == 0) {
      return 0;
    } else {
      return fib(n - 1) + fib(n - 2);
    }
  }

Tomas M. replied on Thu, 2012/07/26 - 6:45am

Correct me if i'm wrong but Fibonacci sequence actually goes 0,1,1,2,3,5... and not 0,1,2,3,5

Tomas M. replied on Thu, 2012/07/26 - 7:02am

int fib(int n) {
   switch(n) {
      case 1 : return 0;
      case 2 : return 1;
      default: return fib(n-1)+fib(n-2);
   }
}

 Lets remember that in the real world sequence start from 1 to n (not like in developers world where collection starts from 0)

Earnest Dyke replied on Thu, 2012/07/26 - 8:58am

Non-recursive version. 

 

	private int fibonacci(int nth) {
		switch (nth) {
		case 1:
			return 0;
		case 2:
			return 1;
		default:
			int l1 = 0,
			l2 = 1,
			sum = 0;
			for (int i = 3; i <= nth; i++) {
				sum = l1 + l2;
				l1 = l2;
				l2 = sum;
			}
			return sum;
		}
	}

 Corrected for correct Fibonacci sequence. E!

Jake Rathman replied on Fri, 2012/07/27 - 8:31am

Realized that my code wasn't very efficient at all. *hangs head*

Earnest Dyke replied on Thu, 2012/07/26 - 9:02am

Very big difference in performance between the recursive and non-recursive Java versions.

Earnie! 

Rodrigo Garcia replied on Thu, 2012/07/26 - 11:23am

I havent programmed in Java for a while, but I guess it could something like this:

 

int fibo(int n)

{

if(--n < 2) return n;

return fibo(n-1) + fibo(n-2); 

}  

 

 

 

 

 

Vijay Nathani replied on Thu, 2012/07/26 - 12:21pm in response to: Vijay Nathani

Groovy Code for corrected Fibonacci sequence:

def fibonacci(n) {
	if (n <= 1) BigInteger.ZERO
	else if (n == 2) BigInteger.ONE
	else  {
		def lastSum = BigInteger.ZERO
		(3..n).inject(BigInteger.ONE) { sum,sequence ->  def o = lastSum; (lastSum = sum).add(o) }
	}
}
(1..9).each { println fibonacci(it) }

 

Eric Jablow replied on Thu, 2012/07/26 - 2:11pm

The problem with code like:

int fib(int n) {
   switch(n) {
      case 1 : return 0;
      case 2 : return 1;
default: return fib(n-1)+fib(n-2);
}
}

is that you will in the midst of computing fib(20), you will call fib(10) a total of  fib(20 - 10) times.  Consider instrumenting the code:

 private int counter = 0; // Getter, resetter elided
 int fib(int n) {
    counter++; 
switch(n) {
case 1 : return 0;
case 2 : return 1;
default: return fib(n-1)+fib(n-2);
}
}
After you call fib(20), counter will equal fib(20) too.

The function fib is a pure function of its argument; you should only be calling fib(10) once if possible. You can cache your results, you can call results in separate threads and halt calls when another thread succeds in computing the value, or you can use generators as in the Groovy code given.  Or, you can use formulas to divide and conquer:

fib(n+m)     = fib(n-1) * fib(m) + fib(n) * fib(m+1)
fib(2*n) = fib(n) ( fib(n-1) + fib(n+1) //Letting m = n
fib(2*n - 1) = fib(n-1)^2 + fib(n)^2 //Letting m = n-1.

So, computing fib(15) leads to fib(7) and fib(8), etc.

 

 

Marek Dec replied on Fri, 2012/07/27 - 2:02am

As Eric says, this can be done much faster using a proper algorithm. I guess the syntaxis does not really matter here. What's important is that the n-th element can be calculated in O(log n) time using a divide and conquer algorithm.

I ran through a cool and understandable solution some time ago. It was based on the fact that following equality is true. 

So the only thing to do is to raise the matrix to a power of n in logarithmic time (and I guess this is pretty straighforward).

I blogged a bit on that and posted some code on the internets: http://marekdec.wordpress.com/2012/07/26/some-fibonacci/

Yaroslav Borovikov replied on Fri, 2012/07/27 - 1:08am

Bruteforce solution in Haskell: 
fib 0 = 0
fib 1 = 1
fib n = fib(n - 1) + fib(n - 2)

ebenezer raj replied on Sat, 2012/07/28 - 9:48pm

using q

{last {x,sum -2#x}/[x-2;til 2]}10

to get the 10th sum = 34

Andre Onuki replied on Wed, 2012/08/01 - 7:26am

This a recursive version that runs in linear time, ie. O(n), unlike most that run in O(n^2). There's room for improvement using BigIntegers, and other little small tweaks.
public class Fib {

    public static int fib(int n) {
        return fib(0, 1, n);
    }

    private static int fib(int a, int b, int n) {
        if (n == 0) {
            return a;
        }
        if (n == 1) {
            return b;
        }
        return fib(b, a + b, n - 1);
    }

    public static void main(String args[]) {
        for (int i = 0; i < 10; i++) {
            System.out.println(Fib.fib(i));
        }
    }
}

Joe Colburn replied on Thu, 2012/09/13 - 10:30pm

Returns 13:

 

function fib($n) {
    $curr = 1;
    $last = 0;
    if ($n == 1) {
        return 0;
    }
    for ($i=0; $i < $n-1; $i++) { 
        $prevcurr = $curr;
        $curr = $curr + $last;
        $last = $prevcurr;
    }

    return $last;
}

echo fib(8); 

 

Marco González replied on Thu, 2012/12/20 - 5:48pm

This is a O(1) implementation.

from math import *

def fib_n(n):
  sqrt5 = sqrt(5)
  return round((pow((sqrt5+1)/2, n) - pow(-1, n)*pow((sqrt5-1)/2, n)) / sqrt5)

To reach to this formula, a lot of mathematical work is needed, involving linear transformations, diagonalization (eigenvalues and eigenvectors), and lots of matrix properties.

But the result is worth!, it doesn't even seem to evaluate the Fibonacci number.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.