Google Treasure Hunt 2008 – Del 1

package GoogleTreasureHunt2008;
import java.math.BigInteger;

public class GoogleBotSolver
{
  private BigInteger[][] results;
  public GoogleBotSolver(int w, int h)
  {
    results = new BigInteger[w][h];
    for (int x = 0; x < w; x++)
    {
      for (int y = 0; y < h; y++)
      {
        results[x][y] = null;
      }
    }
    System.out.println(C(w - 1, h - 1).toString());
  }
  private BigInteger C(int x, int y)
  {
    if (results[x][y] != null) return results[x][y];
    BigInteger res;
    if (x == 0 && y == 0)
    {
      res = BigInteger.ZERO;
    }
    else if (x == 0 || y == 0)
    {
      res = BigInteger.ONE;
    }
    else
    {
      res = C(x - 1, y).add(C(x, y - 1));
    }
    results[x][y] = res;
    return res;
  }
  public static void main(String[] args)
  {
    GoogleBotSolver gbs = new GoogleBotSolver(38, 58);
  }
}

Svaret for W=38 og H=58 som herover er 194937478788574958222679204. Så robotten har rigtigt nok et par muligheder at vælge imellem.

Opgaven er iøvrigt en velkendt afart af Pascal’s trekant.