Fibonacci

public class Fib {
	
	public static void main(String[] args) {	
		
		int initialNumber = 10;		
		int resp ; 
		
		resp = calc(initialNumber);
		
		System.out.println(resp);
	}
	
	public static int calc(int number) { 
						
		if ( number <= 2 ) {
			return 1 ;						
		} else {
			return  calc(number-1) + calc(number-2);
		}	
	}

}

class Fibonacci2 {
    // fibonacci (0) = 0
	// fibonacci (1) = 1
	// fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
	public static long fibonacci (int n, long current, long next) {
	    if (n == 0) return current;
		else return fibonacci (n - 1, next, current + next);
	}
	public static void main(String[] args) {
	    System.out.println ("0->" + fibonacci (0, 0, 1)); // 0
	    System.out.println ("1->" + fibonacci (1, 0, 1)); // 1
	    System.out.println ("40->" + fibonacci (40, 0, 1)); // deve imprimir 102334155
	}
}

import java.util.*;
import java.math.*;

/**
 * "Memoizing" (que eu vou traduzir por "memorização") é uma técnica de acelerar programas
 * recursivos guardando resultados já calculados.
 * Embora existam maneiras mais simples e eficientes de calcular os números de Fibonacci, vou
 * mostrar uma técnica genérica que não exige mexer muito no seu algoritmo.
 * Como vocês devem saber:
 * fibonacci (0) = 0
 * fibonacci (1) = 1
 * fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
 */
class FibonacciComMemorizacao {
	
	Map<Integer,BigInteger> preCalculado = new TreeMap<Integer,BigInteger>();
	
	public FibonacciComMemorizacao() {
		preCalculado.put (0, BigInteger.ZERO); // fibonacci (0) = 0
		preCalculado.put (1, BigInteger.ONE); // fibonacci (1) = 1
	}
	
	public BigInteger fibonacci (int n) {
		if (n == 0) {
			return BigInteger.ZERO;
		} else if (n == 1) {
			return BigInteger.ONE;
		} else if (n > 1) { // fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
			BigInteger f = preCalculado.get (n); // vamos ver se já foi calculado antes...
			if (f != null) {
				// volto o valor pré-calculado!
				return f;
			} else {
				// Não tem jeito, tem de calcular pela fórmula recursiva
				f = fibonacci (n - 1).add (fibonacci (n - 2));
				// E agora vamos guardar o resultado
				preCalculado.put (n, f);
				return f;
			}
		} else {
			throw new IllegalArgumentException ("Definido apenas para os números positivos.");
		}
	}

    public static void main(String[] args) {
		FibonacciComMemorizacao fcm = new FibonacciComMemorizacao();
		int[] valores = {
			1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35, 40, 1000, 3000, 5000
		};
		/*
		Valores esperados: (veja a seqüência http://www.research.att.com/~njas/sequences/A000045)
Fibonacci (1) = 1
Fibonacci (2) = 1
Fibonacci (3) = 2
Fibonacci (4) = 3
Fibonacci (5) = 5
Fibonacci (6) = 8
Fibonacci (7) = 13
Fibonacci (8) = 21
Fibonacci (9) = 34
Fibonacci (10) = 55
Fibonacci (15) = 610
Fibonacci (20) = 6765
Fibonacci (25) = 75025
Fibonacci (30) = 832040
Fibonacci (35) = 9227465
Fibonacci (40) = 102334155		
		 */
		for (int i = 0; i < valores.length; ++i) {
			System.out.println ("Fibonacci (" + valores[i] + ") = " + fcm.fibonacci (valores[i]));
		}
	}
}

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class FibonacciMemoizado
{
    private static List<BigInteger> list = new ArrayList<BigInteger>(0);

    public static void main(String[] args)
    {
        int numero = 1000;

        System.out.println(fibMem(numero));
    }

    public static BigInteger fibMem(int n)
    {
        if (n < list.size())
            return list.get(n);
        else
        {
            BigInteger resultado;

            if (n <= 1)
                resultado = new BigInteger(Integer.toString(n));
            else
                resultado = (fibMem(n - 2).add(fibMem(n - 1)));

            list.add(resultado);

            return resultado;
        }
    }
}