Lógica de Sequencia de Fibonnaci

Programação Java
#1

Fala Galera…
To precisando de uma ajudona…
tenho que desenvolver um programa que calcule a sequencia de fibonnacci e nao tenho a minima ideia de como comecar, os códigos eu sei de cabeça mas a logica to penando pra resolver…
por favor me ajudem se possivel

1 curtida
#2

Segue aee…
http://www2.fundao.pro.br/articles.asp?cod=18

OU
http://ctp.di.fct.unl.pt/~pg/docs/Braga.pdf

Falos.

#3

A sequencia de fibonnacci não é aquela em que o próximo valor é a soma dos dois anteriores:

1 - 1 - 2 - 3 - 5 - 8 - 13 - 21 - etc…

A lógica é muito simples: o proximo número da lista é a soma dos dois anteriores.
Conseguiu entender?

Espero ter ajudado…

#4

n -> f(n)
0 -> 1
1 -> 1
2 -> 2
3 -> 3
3 -> 5
4 -> 8

forma recursiva para encontrar o iesimo termo da série de fibonacci

int fibonacci(int i){ return (i<2)? 1 : fibonacci(i-1) + fibonacci(i-2); }

Entretanto é muito melhor partir pela forma iterativa :wink:

#5

Olá amigo, também tive que fazer esse exercicio.
Vou postar meu código aqui, quem sabe lhe ajuda a compreender o processo…
Também estou dando os primeiros passos no JAVA, qualquer coisa posta ai.
Espero ter ajudado cara, até mais…:wink:

class Fibonacci { public static void main(String[] args) { for(long v1 = 1, v2 = 1, v3, vezes = 0; vezes <= 100; vezes++) { if(vezes == 0) { System.out.println("0"); } if(vezes < 2) { System.out.println("1"); } if(vezes > 2) { v3 = v1 + v2; v1 = v2; v2 = v3; System.out.println(v3); } } } }

#6

Pessoal, sou iniciante e também fiz esse exercício.

Fiz de duas maneiras, da forma recursiva e iterativa:

long fibA(int n) {
	return (n &lt= 1) ? n : fibA(n - 1) + fibA(n - 2);
}

E da forma iterativa. Essa foi uma tentativa de criar um metodo recursivo, mas acabou saindo iterativo:

long fibB(int n) {
	long[] array;
	if (n &lt 1) {
		return n;
	} else {
		array = new long[n + 1];
		for (int x = 0; x &lt array.length; x++) {
			if (x &lt= 1) {
				array[x] = x;
			} else {
				array[x] = array[x - 1] + array[x - 2];
			}
		}
		return array[n];
	}
}

A questão é que na apostila que estou lendo segue o seguinte desafio:
Faça com que a versão recursiva seja tão boa quanto a iterativa.

Eu estou ha um tempão tentando e não consegui pensar em nenhum algoritimo recursivo que não demore para calcular o Fibonacci &gt 50.

Alguem tem alguma luz… não precisa ser a resposta mas apenas uma direção…

Obrigado

#7

Para a versão recursiva sair tão boa quanto a iterativa, você pode aproveitar sua idéia de usar os resultados pré-calculados.

Dica: altere a forma de chamar o seu método, para incluir o array contendo os resultados pré-calculados.

Em vez de:
int fibonacci(int i){
return (i&lt2)? 1 : fibonacci(i-1) + fibonacci(i-2);
}
use algo como:

int fibonacci (int n, int[] precalculado) {
    ... // fica por sua conta
}

...
int[] precalculado = new int[100];
System.out.println (fibonacci (50, precalculado));
...
#8

Obrigado thingol !

não tinha pensado em passar o array dos pré-calculados.
Vou implementar dessa forma e depois eu posto o método aqui.

#9

Pode ser em Python ?

def fib(n):
    a, b = 0, 1
    while b < n:
        print b,
        a, b = b, a+b
#10

Mais uma maneira, só que com while, baseado no exemplo do colega acima:

int V1 = 1, V2 = 1, V3, Vezes = 0;
while (Vezes < 100){
	if (Vezes == 0) {
		System.out.println("0");
	}
		if (Vezes < 2) {
			System.out.println("1");	
		}
		
			if(Vezes > 2) {
			V3 = V1 + V2;
			V1 = V2;
			V2 = V3;
			System.out.println(V3);	
			}
Vezes = Vezes + 1;
}

:-o

#11

sou novo tbm nessa area…porem iniciei no python…qeria saber s poderiam me ajudar…como ficaria essa sequencia em python…em java fica bm mais facil…porem me respondam em python.ok obrigado

#12

Com AspectJ e Java ficaria assim:

Aspect


import java.util.HashMap;
import java.util.Map;


public aspect OptimizeFibonacciAspect 
{
	pointcut fibonacciOperation (int i) : call (int *.fibonacci(int)) && args(i);
	
	pointcut topLevelFibonacciOperation(int i): fibonacciOperation(i) &&
	!cflowbelow(fibonacciOperation(int));
	
	private Map fibonacciCache = new HashMap();
	
	before (int i) :topLevelFibonacciOperation(i)
	{
		System.out.println("Achou anterior para calculo fibonacci "+i);
	}
	
	int around (int i) : fibonacciOperation(i) 
	{
		Object cachedValue = fibonacciCache.get(new Integer(i));
		
		if (cachedValue != null )
		{
			System.out.println("Achou valor no cahe para "+i + ": "+cachedValue);
			return ((Integer)cachedValue).intValue();
		}
	return proceed(i);
	}
	
	after(int i) returning(int result) : topLevelFibonacciOperation (i)
	{
		fibonacciCache.put(new Integer (i), new Integer (result));
	}
}

Classe Java


public static int fibonacci(int i)
	{
		
		return (i<2)? 1 : fibonacci(i-1) + fibonacci(i-2);
	}

Poderia ter um ganho de performance ao procurar o valor anteriror no HashMap

Só fazendo um benchmark para saber …

Utilizei essa mesma metodologia em um fatorial e ficou ótimo …

#13