Coding Contest

Ye' old general discussion board. Basically, for everything that isn't covered elsewhere. Come here to shoot the breeze, shoot your mouth off, or whatever suits your fancy.
This forum is not for asking programming related questions.

Moderator: General Moderators

Grim...
DevNet Resident
Posts: 1445
Joined: Tue May 18, 2004 5:32 am
Location: London, UK

Coding Contest

Post 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!
User avatar
Nathaniel
Forum Contributor
Posts: 396
Joined: Wed Aug 31, 2005 5:58 pm
Location: Arkansas, USA

Post 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
Grim...
DevNet Resident
Posts: 1445
Joined: Tue May 18, 2004 5:32 am
Location: London, UK

Post 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;
}
User avatar
JayBird
Admin
Posts: 4524
Joined: Wed Aug 13, 2003 7:02 am
Location: York, UK
Contact:

Post by JayBird »

how about the shortest code snippet to acheive the task?
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Post by pickle »

I think that's affectionately called 'Golf'.
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
R4000
Forum Contributor
Posts: 168
Joined: Wed Mar 08, 2006 12:50 pm
Location: Cambridge, United Kingdom

Post 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)
programmermatt
Forum Commoner
Posts: 65
Joined: Tue Mar 15, 2005 5:03 pm
Contact:

Post by programmermatt »

Code: Select all

function getFibanacci($n){
    if($n == 1) return 1;
    return getFibanacci($n-1) + getFibanacci($n-2);
}
User avatar
R4000
Forum Contributor
Posts: 168
Joined: Wed Mar 08, 2006 12:50 pm
Location: Cambridge, United Kingdom

Post by R4000 »

Code: Select all

function g($n){
    if($n==1) return 1;
    return g($n-1)+g($n-2);
}
:P still smaller :P
Grim...
DevNet Resident
Posts: 1445
Joined: Tue May 18, 2004 5:32 am
Location: London, UK

Post by Grim... »

For ease of reading, I think we should assume that variable names and whitespace don't count toward the overall size.
programmermatt
Forum Commoner
Posts: 65
Joined: Tue Mar 15, 2005 5:03 pm
Contact:

Post 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.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

just to note, recursion in this case will blow your stack and force php to fault the script.
programmermatt
Forum Commoner
Posts: 65
Joined: Tue Mar 15, 2005 5:03 pm
Contact:

Post 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 :)
User avatar
Luke
The Ninja Space Mod
Posts: 6424
Joined: Fri Aug 05, 2005 1:53 pm
Location: Paradise, CA

Post by Luke »

I need to take some math classes
User avatar
Nathaniel
Forum Contributor
Posts: 396
Joined: Wed Aug 31, 2005 5:58 pm
Location: Arkansas, USA

Post by Nathaniel »

It's more being able to analyze a problem than "math", although the skills you learn in math would help with that.
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post 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.
Post Reply