Created
March 6, 2012 03:11
-
-
Save heslei/1983172 to your computer and use it in GitHub Desktop.
Fibonacci recursive, cache and iterable
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]))); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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"); | |
} | |
} | |
} | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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