sequencia fibonaci

[jassak 0]

Estou comecando no java e estou com dificuldade em calcular a sequencia de fibonaci..

sera que alguem pode me ajudar..

[Kandrade 7]

Claro que podemos ajudar.

 

Sua dúvida está na lógica ou nos comandos do java?

Se conseguiu fazer alguma coisa por favor poste pra gente.

 

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

[ClaudinhU 0]

Poste a sequencia tbm...

 

Pq eu n lembro!

 

^^

[Kandrade 7]

A sequencia é:

 

1, 1, 2, 3, 5, 8, 13 ...

 

Poste a sequencia tbm...

 

Pq eu n lembro!

 

^^

[ClaudinhU 0]

public class FibonacciCalculator  
{  
   // declaração recursiva do método fibonacci   
   public long fibonacci( long number )							 
   {																
	  if ( ( number == 0 ) || ( number == 1 ) ) // casos básicos  
		 return number;											 
	  else // passo da recursão										
		 return fibonacci( number - 1 ) + fibonacci( number - 2 );  
   } // fim do método fibonacci  
 
   public void displayFibonacci(int n)  
   {  
	  for ( int counter = 0; counter <= n; counter++ )  
		 System.out.printf( "Fibonacci of %d is: %d\n", counter,  
			fibonacci( counter ));  
   } // fim do método displayFibonacci  
} // fim da classe FibonacciCalculator

Pode testar que da certo...

 

> FibonacciCalculator fc = new FibonacciCalculator();
> fc.displayFibonacci(10)
Fibonacci of 0 is: 0
Fibonacci of 1 is: 1
Fibonacci of 2 is: 1
Fibonacci of 3 is: 2
Fibonacci of 4 is: 3
Fibonacci of 5 is: 5
Fibonacci of 6 is: 8
Fibonacci of 7 is: 13
Fibonacci of 8 is: 21
Fibonacci of 9 is: 34
Fibonacci of 10 is: 55

http://forum.imasters.com.br/public/style_emoticons/default/grin.gif

 

MAS...entenda o código...não copie apenas!

[_Isis_ 202]

É... esse dá pra começar,mas é ruim porque reduz tudo a somas de 1.

O melhor jeito que eu conheço é a fórmula de Binet:

 

F(n) = (1/sqrt(5)) * { [ (1+sqrt(5))/2] ⁿ - [ (1- sqrt(5))/2 ] ⁿ }

[ClaudinhU 0]

O melhor jeito de fazer é com Array...

 

Mas fiquei com preguiça...dai decidi fazer assim...depois eu faço com Array pra mostrar...

 

=)

 

Obs.: Eu nunca ouvi falar nessa fórmula!

[_Isis_ 202]

Essa fórmula é parada obrigatória em livros de Matemática Discreta.

[ClaudinhU 0]

Na realidade...

 

O melhor jeito é com RECURSIVIDADE...

 

public int fibonacci (int n) {  
  if (n == 1 || n == 2) return 1;  
  else return fibonacci(n-1) + fibonacci(n-2);

[Kandrade 7]

Recursividade é bom em certos casos, mas nem sempre.

Principalmente se a entrada é grande.

[_Isis_ 202]

Recursividade é o pior nesse caso.

 

Se n=7:

 

1) FIB(7) = return fib(6)+fib(5)

2) FIB(5) = return fib(4)+fib(3)

3) FIB(4) = return fib(3)+fib(2)

4) FIB(3) = return fib(2)+fib(1)

5) FIB(2) = return 1

4') FIB(3) = return 1+fib(1)

6) FIB(1) = return 1

4'') FIB(3) = return 2

3') FIB(4) = return 2 + fib(2)

7) FIB(2) = return 1

3'') FIB(4) = return 3

2') FIB(5) = return 3 + fib(3)

8) FIB(3) = return fib(2) + fib(1)

9) FIB(2) = return 1

8') FIB(3) = return 1+fib(1)

10) FIB(1) = return 1

8'') FIB(3) = return 2

2'') FIB(5) = return 5

1') FIB(6) = return fib(6)+fib(5)

 

 

Através da recursão você reduz tudo a somas de 1,o que é bem estúpido de se fazer.A versão iterativa é um pouco mais inteligente:

 

fibN_1 = 1
fibN_2 = 1
fibN = 1

while N>2:
fibN = fibN_1 + fibN_2
fibN_1,fibN_2 = fibN,fibN_1
N-=1

print fibN

 

A verão iterativa tem complexidade O(N). Dê uma olhada na complexidade da recursiva: http://www.brpreiss.com/books/opus4/html/page73.html . A versão recursiva cresce exponencialmente à medida que N aumenta.

 

 

A fórumla de Binet dá complexidade O(1) se você desconsiderar a implementação em software da exponenciação. Mas se for p/ levar em conta esse cálculo, existem métodos que levam 2*[log₂ N] ( [] é a função piso).

[ClaudinhU 0]

Eu disse que recursividade é a melhor saída pq um cara com 7 certificações java disse isso em outro fórum...

 

Pelas certificações dele...ele parecia conhecer...mas pelo visto...certificação não é tudo!

[Mário Monteiro 179]

Eu disse que recursividade é a melhor saída pq um cara com 7 certificações java disse isso em outro fórum...

 

Pelas certificações dele...ele parecia conhecer...mas pelo visto...certificação não é tudo!

Tem casos e casos ... Uma escolha de solução nao pode ser verdade para todas as ocorrencias

[ClaudinhU 0]

Eu disse que recursividade é a melhor saída pq um cara com 7 certificações java disse isso em outro fórum...

 

Pelas certificações dele...ele parecia conhecer...mas pelo visto...certificação não é tudo!

Sim...ele havia dito isso sobre a sequencia de Fibonacci mesmo...

 

Eu havia feito com for...mas ele disse que com recursividade é o meio mais rápido de fazer...e o que usa menos processamento...

[_Isis_ 202]

A versão recursiva abusa muito mais da pilha do que a iterativa ou a fórmula de binet.

Além disso,você não aproveita os resultados anteriores,sempre repetindo o cálculo (e enchendo mais ainda a pilha)

 

Na iterativa você tem basicamente, em Assembly, as instruções beq,jmp e 5 add. Na recursiva, existem 5 add (supondo que a JVM usa registradores,mas provavelmente deve ficar tudo numa pilha), 2 beq e ainda por cima tem o trabalho de empilhar o argumento e o endereço de retorno (e sabe-se lá mais o quê...stack pointer,base pointer e outras coisas exóticas da arquitetura,seja lá o nome que isso tiver na JVM).

 

Me faz falta um livro decente sobre a arquitetura da JVM.