Monthly Archives: March 2005

Formatted input

Posted by timvw on March 19, 2005 None comments

I was in need for formatted input and the decomposition of the input into a stream of tokens so i came up with the following:

And now i am ready for formatted input like this:

public class Main {
  public static void main(String[] args) {
    try {
      BufferedReader input = new BufferedReader(new FileReader("file.txt"));
      for (String in = input.readLine()) {
        TokSequence ts = new TokSequence(new StringTokenizer(in));
        int userId = ts.getIn();
        double score = ts.getDouble();
        String name = ts.getString();
        // do stuff with userId, score and name
      }
    } catch (Exception e) {
      System.err.println(e);
      System.exit(1);
    }
  }
}

More on recursion

Posted by timvw on March 4, 2005 None comments

Yesterday i already wrote that an interative implementation for a recursive function is more efficient. And i gave you an example of the fibonacci function. Well, today i’m here to present you an implementation for every recursive function.

class Math
{
    // calculate the linear combination
    // fe:
    // coefficients = array(1, 2, 3)
    // values = array(4, 5, 6)
    // returns:  (1 * 4) + (2 * 5) + (3 * 6)
    function lc($coefficients, $values)
    {
        if (count($coefficients) != count($values))
        {
            return false;
        }

        $result = 0;
        for ($i = 0; $i < count($coefficients); ++$i)
        {
            $result += $coefficients[$i] * $values[$i];
        }
        return $result;
    }

    // lookup the value for the recursive function
    // fe:
    // n: 3
    // coefficients = array(a, b)
    // initvalues = array(0, 1)
    // returns: 2
    // this is the same as f(n) = (a * (n-2)) + (b * (n-1))
    function recursive($n, $coefficients, $initvalues)
    {
        if ($n < count($initvalues))
        {
            return $initvalues[$n];
        }

        for ($i = count($initvalues); $i <= $n; ++$i)
        {
            $result = Math::lc($coefficients, $initvalues);
            array_shift($initvalues);
            array_push($initvalues, $result);
        }
        return $result;
    }
}

As an example we use this class to calculate fibonacci(3):

$coefficients = array(1, 1); // f(n) = (1 * f(n-2)) + (1 * f(n-1))
$initvalues = array(0, 1); // f(0) = 0 and f(1) = 1
echo Math::recursive(3, $coefficients, $initvalues);

Calculating Fibonacci

Posted by timvw on March 3, 2005 None comments

What is a recursive function? It is a function where the value for input n is calculated as a linear combination of the previous 1, 2, …, n-1 function values. An example is the fibonacci function: f(n) = f(n-1) + f(n-2).

If we program this our first code would look like:

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

It becomes clear that this is really inefficient. For example if we call fibonacci(3) the following function calls will be made:
fibonacci(3)
– fibonacci(2)
—- fibonacci(1)
—- fibonacci(0)
– fibonacci(1)

We can optimize this function by implementing it as an iteration. We still have to calculate all the previous values, thus the time-complexity of this algorithm is O(n). Here is the code:

function fibonacci($n)
{
  if ($n < = 1)
  {
    return $n;
  }

  $nmin2 = 0;
  $nmin1 = 1;
  $result = 0;

  for ($i = 2; $i <= n; ++$i)
  {
    $result = $nmin1 + $nmin2;
    $nmin2 = $nmin1;
    $nmin1 = $result;
  }
  return $result;
}

Time to take our math course and lookup a non-recursive function for fibonacci. Eureka, we have found one! The algorithm has constant time complexity. The proof for this function is can be found here.

function fibonacci($n)
{
  $denominator = pow((1+sqrt(5))/2, $n) - pow((1-sqrt(5))/2, $n);
  $nominator = sqrt(5);
  return $denominator / $nominator;
}