Skip to content

Instantly share code, notes, and snippets.

@heslei
Created March 6, 2012 03:11
Show Gist options
  • Save heslei/1983172 to your computer and use it in GitHub Desktop.
Save heslei/1983172 to your computer and use it in GitHub Desktop.
Fibonacci recursive, cache and iterable
public class Fibonacci {
public int fibonacciDe(int n){
if(n <= 0){
return 0;
}
if (n == 1){
return 1;
}
return fibonacciDe(n-1) + fibonacciDe(n-2);
}
public static void main(String[] args){
System.out.print("Fib " + new Fibonacci().fibonacciDe(Integer.parseInt(args[0])));
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class FibonacciCache {
private int[] cache = new int[1000];
public FibonacciCache(){
// n de 1 = 1;
cache[1] = 1;
}
public int fibonacciDe(int n){
if(cache[n] != 0){
return cache[n];
}
// n de 0 = 0
if(n <= 0){
return 0;
}
int result = fibonacciDe(n-1) + fibonacciDe(n-2);
cache[n] = result;
return result;
}
public static void main(String[] args) throws Exception{
String inputLine = "";
InputStreamReader converter = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(converter);
FibonacciCache fib = new FibonacciCache();
while (!(inputLine.equals("sair"))){
System.out.println("Informe o valor de n para obter o seu Fibonacci ou \"sair\" para finalizar: ");
inputLine = in.readLine();
if (!(inputLine.equals("sair"))){
int value = Integer.parseInt(inputLine);
long begin = System.currentTimeMillis();
System.out.print("Fibonacci de "+ inputLine + " é: " + fib.fibonacciDe(value) +"\n");
long end = System.currentTimeMillis();
System.out.print("Tempo " + (end - begin) + "\n");
}
}
}
}
import java.util.Iterator;
public class FibonacciIterator implements Iterable<Integer>{
private int n = 0;
private int index = -1;
// n-1 e n-2 iniciais
private int n_1 = 1;
private int n_2 = 0;
public FibonacciIterator(int n){
this.n = n;
}
private int fibonacciDe(int n){
if(n <= 0){
return 0;
}
if (n == 1){
return 1;
}
int result = n_1 + n_2;
n_2= n_1;
n_1 = result;
return result;
}
public Iterator<Integer> iterator(){
return new FibIterator();
}
public static void main(String[] args){
int value = Integer.parseInt(args[0]);
FibonacciIterator fib = new FibonacciIterator(value);
Iterator iter = fib.iterator();
System.out.print("Fibonacci de " + value + ":");
while(iter.hasNext()){
System.out.print(" " + iter.next());
}
}
class FibIterator implements Iterator<Integer>{
public boolean hasNext(){
return index < n;
}
public Integer next(){
if(!hasNext()){
return null;
}
return fibonacciDe(++index);
}
public void remove(){
throw new RuntimeException("Do nothing");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment