1. 
/**
* Angewandte Mathematik, SS11
* 495 - Fibonacci Freeze
* http://uva.onlinejudge.org/external/4/495.pdf
* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-04-17 21:14:32
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.412
*/

import java.io.*;
import java.math.BigInteger;

public class Main
{
// static computing of an array with the fibonacci numbers
// advantage vs. recursion: computed numbers are stored and dont have to be computed again.
static BigInteger[] fibonArr = fibonacciArr(5001);

static BigInteger[] fibonacciArr(int n)
{
BigInteger[] fibonArr= new BigInteger[n];
fibonArr[0] = BigInteger.valueOf(0);
fibonArr[1] = BigInteger.valueOf(1);
for(int i = 2; i < n; i++)
fibonArr[i] = fibonArr[i-2].add(fibonArr[i-1]);
return fibonArr;
}

public static final void main(String args[])
{
try
{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String s;

while(true)
{
s = input.readLine();
if(s.isEmpty())
System.exit(0);
int number = Integer.valueOf(s);
BigInteger fibon = fibonArr[number];
System.out.println("The Fibonacci number for "+number+" is "+fibon);
}
}
catch(Exception e){}
}
}


2.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem: 495 Fibonacci Freeze
* Link: http://uva.onlinejudge.org/external/4/495.pdf
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 12/04/2011
*
* Method : BigInteger
* Status : Accepted
* Runtime: 2.008
*/


public class Main
{
static Map<Integer, BigInteger> fibs = new HashMap<Integer, BigInteger>();

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int number;

while(sc.hasNextInt())
{
number = sc.nextInt();
System.out.println("The Fibonacci number for " + number + " is " + getFibonacci(number));
}
}

/**
* Gibt die n-te Fibonaccizahl zur¾ck
* @param n >=0
* @return n-te Fibonaccizahl
*/
public static BigInteger getFibonacci(int n)
{
BigInteger tmp;
if(fibs.containsKey(n))
{
return fibs.get(n);
}
else if(n==0)
{
tmp = new BigInteger("0");
}
else if(n==1)
{
tmp = new BigInteger("1");
}
else
{
tmp = getFibonacci(n-1).add(getFibonacci(n-2));
}
fibs.put(n, tmp);
return tmp;
}
}

3.


/**
* Angewandte Mathematik, SS11
* Problem: 495 - Fibonacci Freeze
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2113
*
* @author Schramm, Felix
* @author Vogel, Johannes
* @version 1.0, 04/18/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.756
*/



import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main (String args[]) {
Scanner input = new Scanner(System.in);
while(input.hasNextInt()){
int number = input.nextInt();
System.out.println("The Fibonacci number for "+number+" is "+fib(number));
}
}

private final static BigInteger TWO = BigInteger.valueOf(2);

public static BigInteger fib(int value) {
BigInteger n = BigInteger.valueOf(value); // Konvertierung
if (n.compareTo(BigInteger.ONE) <= 0) { // Wenn 0 oder 1, 0 oder 1 zurück
return n;
}

BigInteger x = BigInteger.ONE; // Konstanten erstellen
BigInteger y = BigInteger.ZERO;

for (int k = n.bitLength() - 2; k >= 0; k--) { // Berechnung (trivial ;-)
BigInteger powered = x.pow(2);
x = powered.add(TWO.multiply(x).multiply(y));
y = powered.add(y.pow(2));
if (n.testBit(k)) {
BigInteger temp = x;
x = x.add(y);
y = temp;
}
}
return x;
}
}