Page 1 of 3

Coding Contest

Posted: Tue Apr 04, 2006 6:36 am
by Grim...
We haven't had a coding contest for a while, so here is a little challenge:
Assuming a user-entered integer to be $n, write a function to find what the nth number in the Fibonacci squence is.
The Fibonacci sequence is:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

So if $n was 7, the function would return 13.

Get to it!

Posted: Tue Apr 04, 2006 7:48 am
by Nathaniel

Code: Select all

<?PHP
class Fibonacci
{
	var $_n = 0;
	
	function Fibonacci($n)
	{
		$this->_n = $n;
	}
	
	function nthNumber()
	{
		if ( $this->_n <= 2 )
		{
			return 1;
		}
		
		$i = new Fibonacci($this->_n - 2);
		$j = new Fibonacci($this->_n - 1);
		
		return $i->nthNumber() + $j->nthNumber();
	}
}
?>
And the unit test (using SimpleTest):

Code: Select all

<?PHP
class FibonacciTestCase extends UnitTestCase
{
	var $sequence = array
	( 
		1 => 1, 
		2 => 1, 
		3 => 2, 
		4 => 3,
		5 => 5, 
		6 => 8, 
		7 => 13, 
		8 => 21, 
		9 => 34, 
		10 => 55, 
		11 => 89, 
		12 => 144, 
		13 => 233, 
		14 => 377, 
		15 => 610, 
		16 => 987
	);		
		
	function testOneReturnsOne()
	{
		$fib = new Fibonacci(1);
		$this->assertIdentical($fib->nthNumber(), 1);
	}
	
	function testTwoReturnsOne()
	{
		$fib = new Fibonacci(2);
		$this->assertIdentical($fib->nthNumber(), 1);
	}
	
	function testEntireSequence()
	{
		foreach ( $this->sequence as $n => $number )
		{
			$fib = new Fibonacci($n);
			$this->assertIdentical($fib->nthNumber(), $number);
		}
	}
}
?>
Yay!

- Nathaniel

Posted: Tue Apr 04, 2006 8:02 am
by Grim...
Here's mine:

Code: Select all

function fib_get($n)
{
    if ($n == 1)
    {
        return 1;
    }
    $a = 0;
    $b = 1;    
    for ($i = 2; $i <= $n; $i++) 
    {
        $x = $a + $b;
        $a = $b;
        $b = $x;
    }    
    return $x;
}

Posted: Tue Apr 04, 2006 8:27 am
by JayBird
how about the shortest code snippet to acheive the task?

Posted: Tue Apr 04, 2006 8:34 am
by pickle
I think that's affectionately called 'Golf'.

Posted: Tue Apr 04, 2006 8:34 am
by R4000
heh, in that case... i stole grim's but made it small

Code: Select all

function fib_get($n){
    if ($n == 1) return 1;
    $b = ($a = 0) + 1;
    for ($i = 2; $i <= $n; $i++) {
        $b = ($x = $a + ($a = $b));
    }    
    return $x;
}
heh :P could proberly be made even smaller
(btw, i havent tested this, so it proberly has some errors, but in thery it should work)

Posted: Tue Apr 04, 2006 8:40 am
by programmermatt

Code: Select all

function getFibanacci($n){
    if($n == 1) return 1;
    return getFibanacci($n-1) + getFibanacci($n-2);
}

Posted: Tue Apr 04, 2006 8:44 am
by R4000

Code: Select all

function g($n){
    if($n==1) return 1;
    return g($n-1)+g($n-2);
}
:P still smaller :P

Posted: Tue Apr 04, 2006 9:19 am
by Grim...
For ease of reading, I think we should assume that variable names and whitespace don't count toward the overall size.

Posted: Tue Apr 04, 2006 9:38 am
by programmermatt
There is actually an error in my code, it should be testing for $n==0 in addition to testing for $n==1.

Anyway, I think that for a coding contest the challenge should be more difficult than a well known sequence (with a defined function) being implemented. I remember doing this when I first started programming and learned about recursion.

Posted: Tue Apr 04, 2006 9:47 am
by feyd
just to note, recursion in this case will blow your stack and force php to fault the script.

Posted: Tue Apr 04, 2006 10:03 am
by programmermatt
Wow, now I feel dumb..

Code: Select all

function getFibanacci($n){
    if($n == 1 || $n == 2) return 1;
    return getFibanacci($n-1) + getFibanacci($n-2);
}
High values of $n will not work very well, but my calculator can't handle that either, so it is ok :)

Posted: Tue Apr 04, 2006 3:21 pm
by Luke
I need to take some math classes

Posted: Tue Apr 04, 2006 3:55 pm
by Nathaniel
It's more being able to analyze a problem than "math", although the skills you learn in math would help with that.

Posted: Tue Apr 04, 2006 3:57 pm
by timvw
For larger numbers, this one is much faster ;) (not need to calculate previous ones/ find the proof at mathworld or drmath or ...)

Code: Select all

<?php
function fibonacci($n)
{
  $denominator = pow((1+sqrt(5))/2, $n) - pow((1-sqrt(5))/2, $n);
  $nominator = sqrt(5);
  return $denominator / $nominator;
}
?>
Anyway, i once summed it up all here.