[xclite]

This is a pretty straight forward problem: Create a method that returns the nth value of the Fibonacci sequence in as few characters as possible. Extra points for not repeating work (i.e. for not implementing the naive recursive solution)!

This post has been edited by xclite: 03 October 2012 - 07:01 AM

[Curtis Rutland]

Ok, this is me having never ever used Ruby before. Take this for what it's worth:

def f(i)
	if(i==0||i==1)
		return i
	else
		return f(i-1)+f(i-2)
	end
end

That assumes that i is positive, and f(0) = 0, and f(1) = 1. It's the recursive solution, but like I said, first time with Ruby.

[Skaggles]

This assumes n is positive.

Spoiler

def fib(n)
  n < 2 ? n : fib(n-1) + fib(n-2)
end

[macosxnerd101]

Solving the linear recurrence gives me O(1) time.

Spoiler

def fib(n)
   return Math.sqrt(5)/5 * (((1+Math.sqrt(5))/2)**n - ((1-Math.sqrt(5))/2)**n)
end

[Curtis Rutland]

I guess the question is, which is more important? The efficiency or the pure character count?

[Nallo]

I never used ruby before. This is the shortest I could come up with (not using recursion):

def f(n)
 a,b=0,1
 n.times{a,b=b,a+b}
 a
end

This post has been edited by Nallo: 10 May 2011 - 02:43 AM

[xclite]

Curtis Rutland, on 09 May 2011 - 06:53 PM, said:

I guess the question is, which is more important? The efficiency or the pure character count?

Playing with both is fine - I'd probably do two, one that emphasizes each. Also, I meant to uprep you but in my morning fail-mode I downrepped you so I'm finding two random posts to make up for it.

[WaeV]

Based on macosxnerd101's solution.

Spoiler

def fib(n)
  a = Math.sqrt(5)
  return a/5 * ((1+a)/2)**n - ((1-a)/2)**n
end

This post has been edited by WaeV: 16 May 2011 - 01:35 PM