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

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);
}

still smaller

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.