Coding Contest
Moderator: General Moderators
Coding Contest
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!
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!
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();
}
}
?>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);
}
}
}
?>- Nathaniel
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;
}- R4000
- Forum Contributor
- Posts: 168
- Joined: Wed Mar 08, 2006 12:50 pm
- Location: Cambridge, United Kingdom
heh, in that case... i stole grim's but made it small
heh
could proberly be made even smaller
(btw, i havent tested this, so it proberly has some errors, but in thery it should work)
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;
}(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:
Code: Select all
function getFibanacci($n){
if($n == 1) return 1;
return getFibanacci($n-1) + getFibanacci($n-2);
}-
programmermatt
- Forum Commoner
- Posts: 65
- Joined: Tue Mar 15, 2005 5:03 pm
- Contact:
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.
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.
-
programmermatt
- Forum Commoner
- Posts: 65
- Joined: Tue Mar 15, 2005 5:03 pm
- Contact:
Wow, now I feel dumb..
High values of $n will not work very well, but my calculator can't handle that either, so it is ok 
Code: Select all
function getFibanacci($n){
if($n == 1 || $n == 2) return 1;
return getFibanacci($n-1) + getFibanacci($n-2);
}For larger numbers, this one is much faster
(not need to calculate previous ones/ find the proof at mathworld or drmath or ...)
Anyway, i once summed it up all here.
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;
}
?>