Algorítmo de Fibonacci

18 de setembro de 2008 31 respostas

jbdj 18 de setembro de 2008

Oi Pessoal,

Sou novato em Java, e estou seguindo a apostila do caelum. Me deparei com um problema bastante interessante: implementar a série de Fibonacci até passar de 100, usando apenas duas variáveis. A série de Fibonacci é a seguinte: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Abaixo vai o código usando três variáveis:

int proximo=0,atual=0,anterior=1;
while(proximo<=100){
    proximo=atual+anterior;
	System.out.print(proximo+",");
	anterior=atual;
	atual=proximo;
}

Alguém sabe fazer usando apenas duas variáveis?

Podemos perceber que nos deparamos com a velha situação de trocarmos os valores de duas variáveis. Por exemplo, se quisermos mudar o valor de x para y e de y para x, é necessário a inclusão de uma terceira variável (z):

z=x
x=y
y=z

Alguém sabe informar, se Java possui alguma forma de solucionar este problema sem o uso de uma terceira variável?

Atenciosamente,

João.

31 Respostas

Lanz 18 de set. de 2008 1 like

Mais simples que isso impossivel o.O

public class Fibonacci {
	static {
		for(int a=0, b=1, i=0; i<15; b+=a, a=b-a, i++) {
			System.out.print(a + " ");
		}  
		System.exit(0);
	}
}

Ladim 18 de set. de 2008

E aí velho…

Apesar do monte(e bota monte nisso) de post’s aqui no GUJ falando sobre Fibonacci aqui vai a dica…

Procure sobre RECURSIVIDADE…

Eu acho que é a única maneira de resolver utilizando apenas 2 variáveis.

Até mais.

Ladim.

ViniGodoy 18 de set. de 2008

Esse código não está simples. Ele é uma versão mais enxuta, porém mais complicada, do código anterior.

O que ficaria mais simples é isso aqui:
http://www.guj.com.br/posts/list/57712.java#303559

Bruno_Laturner 18 de set. de 2008

Esse código não está simples. Ele é uma versão mais enxuta, porém mais complicada, do código anterior.

O que ficaria mais simples é isso aqui:
http://www.guj.com.br/posts/list/57712.java#303559

Em compensação introduz um belo StackOverflow, além de ser extremamente lerdo.

ViniGodoy 18 de set. de 2008

Na própria página há um link explicando a tail recursion, além de outra mostrando como resolver o problema com um cache.

Duas técnicas bastante interessantes.

Agora, vale conhecer até pelo cunho acadêmico da solução. Até porque, a maioria dos mortais não vai precisar calcular a seqüência de fibonacci no dia-a-dia.

E isso só introduz um stack overflow se o número for muito grande. Já a questão de ser lerdo, tudo depende da aplicação que você estiver fazendo. Se o calculo de fib for esporádico, não será um problema. Agora, se ela baseia-se nisso, aí realmente é melhor basear-se em uma solução iterativa, ou ter um cache para valores comumente calculados.

dlt 18 de set. de 2008

Prum iniciante é até bom brincar de gerar stack overflows.

Calcula fibonacci de [telefone removido] em todas linguagens que vc conhece, jbdj!

jukkinha 18 de set. de 2008

soh usar a fórmula:

f(n) = [ phi ^ n - (1 - phi) ^ n ] / sqrt(5)

onde phi = [ 1 + sqrt(5) ] / 2

jbdj 18 de set. de 2008 1 like

Lanz:
Mais simples que isso impossivel o.O

public class Fibonacci { static { for(int a=0, b=1, i=0; i<15; b+=a, a=b-a, i++) { System.out.print(a + " "); } System.exit(0); } }

Oi pessoal,

Apesar de Lanz usar três variáveis como mostrado acima, adaptei o algoritmo dele para usar apenas duas variáveis, como segue abaixo:

for(int a=0,b=1;a<=100;b+=a,a=b-a){
	System.out.print(a+",");
}

Dessa forma implementamos a série de Fibonacci até passar de 100 usando apenas duas variáveis, ou seja, problema resolvido.

Gostaria de agradecer ao Lanz e a todos pela grande ajuda.

Atenciosamente,

João.

renzonuccitelli 18 de set. de 2008

Toma aí uma gambiarra pra nao usar outra variável e não usar recursão, que costuma ser difícil pra iniciantes:

public static void main(String[] args) {
		int a,b;
		a=b=1;
		System.out.print("1,1");
		while(b<500){
			System.out.print(","+(a+b));
			if(a>b)
				b+=a;
			else
				a+=b;
		}
		
		

	}

LeoX 28 de jun. de 2011 1 like

Ai vai uma gambiarra iterativa mais entendivel. :lol:

class Fibonacci{ public static void main(String []args){ int num=20; int a=0; int b=1; for(int i=0; i<num; i++){ if(num ==1 || num ==2){ System.out.println(1); } else{ b = b+a; a = b-a; System.out.println(a); } } } }

Stefan_Queiroz 22 de set. de 2011

for (int y = 1, x = 0; y <= 100; y=y)
			{	
   // o println pode ser colocado nesta linha caso prefira.
				y = y + x;
				x = y - x;				
				System.out.println(y);
						
			}

Abç

brunoprogramadorjava 21 de mar. de 2012

Alguém pode me ajudar na lógica???

Quero que por exemplo digitar 8 mostre a sequencia até 8, esse código se você digitar 8 ele mostra 8 números…

package lista02;

import java.util.Scanner;

class Fibonacci {

public static void main(String[] args) {

System.out.println(“Digite um número para o cálculo de finonacci”);

int num = new Scanner(System.in).nextInt();

int a = 0;
	int b = 1;
	for (int i = 0; i < num; i++) {
		if (num == 1 || num == 2) {
			System.out.println(1);
		} else {
			b = b + a;
			a = b - a;
			System.out.println(a);
		}
	}
}

}

dyego.mota 29 de mai. de 2012

brunoprogramadorjava:

Alguém pode me ajudar na lógica???

Quero que por exemplo digitar 8 mostre a sequencia até 8, esse código se você digitar 8 ele mostra 8 números…

package lista02;

import java.util.Scanner;

class Fibonacci {

public static void main(String[] args) {

System.out.println(“Digite um número para o cálculo de finonacci”);

int num = new Scanner(System.in).nextInt();

int a = 0;
	int b = 1;
	for (int i = 0; i < num; i++) {
		if (num == 1 || num == 2) {
			System.out.println(1);
		} else {
			b = b + a;
			a = b - a;
			System.out.println(a);
		}
	}
}

}</blockquote>

Bruno,

Basta remover o “System.out.println(a);” de dentro do “for” <img src="https://cdn.jsdelivr.net/gh/twitter/twemoji@14/assets/72x72/s.pnglight_smile.png?v=9" title=":slight_smile:" class="emoji" alt=":slight_smile:">

Se tiver interesse em uma versão com recursividade:

public class Fibonacci {

int result = 1, i = 1, n1 = 0, n2 = 1;

int calculaFibonacci(int elemento)
{		
	if (elemento == i) 
	{
		return result;
	}
	else
	{
		result = n1 + n2;
		n1 = n2;
		n2 = result;
		i = i + 1; 
		calculaFibonacci(elemento);
		return result;				
	}
}

}

tenho a impressão de que um desses “return” poderia ser modificado, mas aparentemente assim ta funfando bem.

Ai pra vc imprimir o “result” vai coloca na sua main:

Fibonacci fibo = new Fibonacci();

int i = fibo.calculaFibonacci(12);

System.out.println("resultado fibonacci: " + i);

Espero que tenha ajudado.

brunoprogramadorjava 29 de mai. de 2012

valew heim pela dica…

botocudo_killer 29 de mai. de 2012

eu faria dessa forma

public class Fibonacci2 {

public static void main(String[] args) {
int n = 0; 
try { 
n = Integer.parseInt(args[0]); 
} catch (Exception err) { 
System.out.println("Erro... Vc deve passar um número."); 
System.exit(0); 
} 

System.out.print("A série é:"); 
for (int i = 1; i <= n; i++) { 
System.out.print(" " + fibbon(i) + ","); 
} 

} 

public static long fibbon(long n) { 
long fib; 

if (n == 0) { 
fib = 0; 
return fib; 
} else if (n == 1) { 
fib = 1; 
return fib; 

} else { 
fib = fibbon(n - 2) + fibbon(n - 1); 
return fib; 

} 
}
}

Eiro 29 de mai. de 2012

public class Fibonacci {
	
	int a = 1;
	int b = 1;	
	
	int calculafibonacci(int x){
		if (x == 1){
			return 0;			
		}
		for(int i = 1; i < (x-1); i++){
			b = a - b;		
			a = a+b;			
		}		
		return a;
	}		
}

public class Teste {
	public static void main (String[] args){
	Fibonacci fibo = new Fibonacci();
	
	int i = fibo.calculafibonacci(10);
	System.out.println(i);
	}

}

Eiro 30 de mai. de 2012

Gente, eu to com uma duvida aqui num desafio de fibonacci

5.7 - Desaﬁos

No capítulo anterior, você deve ter reparado que a versão recursiva para o problema de Fibonacci é lenta
porque toda hora estamos recalculando valores. Faça com que a versão recursiva seja tão boa quanto a
versão iterativa. (Dica: use arrays para isso)

Eu tenho que criar um Array dentro da class Fibonacci né?
Tenho que criar outra class só pra criar um array?
Como eu faço pra um método retornar um Array?(só com println?)

botocudo_killer 30 de mai. de 2012

O “truque” consiste em utilizar um vetor que armazena termos já calculados (ou seja, nesta solução recursiva nenhum termo é recalculado). Veja que a solução ficou mais complicada - foi necessário criar mais métodos e variáveis auxiliares.

public class Fibonacci {           private static int[] vetAux = new int[50];     private static int k;       public static long fibo(int n) {                    k = 1; // inicializa k              return recursao(n);            }       private static long recursao(int n) {             if (n < 0) {                 return vetAux[0];             } else {             if (k < 3) {               vetAux[n] = k - 1;                k++;             } else {                  vetAux[n] = vetAux[n + 1] + vetAux[n + 2];                   }               return recursao(n - 1);            }     }           public static void main(String[] args) {  // teste do programa. Imprime os 30 primeiros termos     for (int i = 0; i < 30; i++) {         System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");                 }             }         }

Eiro 30 de mai. de 2012

peraí, ficou muito confuso deixa eu ajeitar;

public class Fibonacci {           
               private static int[] vetAux = new int[50];     
               private static int k;       
               public static long fibo(int n) {                    
               k = 1; // inicializa k              
               return recursao(n);            
          }       
             private static long recursao(int n) {             
                        if (n < 0) {                 
                                 return vetAux[0];             
                                      } 
                        else {             
                                 if (k < 3) {               
                                         vetAux[n] = k - 1;                
                                         k++;             
                                               } 
                                else {                  
                                        vetAux[n] = vetAux[n + 1] + vetAux[n + 2];                   
                                       }               
                               return recursao(n - 1);            
                        }     
                }           

public static void main(String[] args) {  // teste do programa. Imprime os 30 primeiros termos     
          for (int i = 0; i < 30; i++) {         
                    System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");                 
                                                }             
                           }         
}

botocudo_killer 30 de mai. de 2012

dessa forma usei RECURSIVA COM VETOR, sendo que seja melhor que a iterativa

Eiro 30 de mai. de 2012

vetor = array?

não entendi aquele return recursao(n); lá em cima como se fosse declarando uma variavel

botocudo_killer 30 de mai. de 2012

em algoritmo sim é a mesma coisa…ate mesmo no java

botocudo_killer 30 de mai. de 2012

vc pelo - executou esse algoritimo?

Eiro 30 de mai. de 2012

não não.. to procurando entender primeiro pra embutir no meu programa..

olha só:

public class Fibonacci {
	
	int a = 1;
	int b = 1;
	int j = 0;

	int[] numero = new int[30];	
	
	int calculafibonacci(int x){
		if (x == 1){
			this.numero[j] = 0;
			j++;
			return 0;
		}
		for(int i = 1; i < (x-1); i++){
			b = a - b;		
			a = a+b;
			this.numero[j] = a;
			j++;
		}
		System.out.println(this.numero[j]);
		return 1;		
	}		
}


public class Teste {
	public static void main (String[] args){
	Fibonacci fibo = new Fibonacci();
	
	int i = fibo.calculafibonacci(10);
	System.out.println(i);
	}

}

o this.numero[j] sempre retorna 0(zero)

eu nao entendi foi o return recursao(n); lá em cima como se fosse declarando uma variavel

Eiro 31 de mai. de 2012

Consegui =D

public class Fibonacci {
	
	int a = 1;
	int b = 1;
	int j = 0;

	int[] numero = new int[11];	
	
	int calculafibonacci(int x){
		if (x == 1){
			this.numero[0] = 0;
			return this.numero[0];
		}
		else{
			this.numero[0] = 0;
			j++;
		}
		for(int i = 1; i < (x-1); i++){
			b = a - b;		
			a = a+b;
			this.numero[j] = a;
			j++;
		}		
		return this.numero[j-1];		
	}		
}

public class Teste {
	public static void main (String[] args){
	Fibonacci fibo = new Fibonacci();
	
	int i = fibo.calculafibonacci(10);
	System.out.println(i);
	}
}

gledsonvc 23 de dez. de 2012

Levando em consideração o que foi explicado até o exercicio da apostila da caelum onde não havia sido explicado recursifidade, pegando em meus arquivos me deparei com esse exercicio respondido.
3.14 Desafios: Fibonacci�

Faça o exercício da série de Fibonacci usando apenas duas variáveis.

class Exercicio1{
	public static void main(String[] args){
		int fibonacci=0;
		int antfibonacci=1;
		System.out.print(fibonacci+", ");
		do{
			if(fibonacci<2){
				fibonacci++;
				System.out.print("1, ");
			}else{
				System.out.print(fibonacci+", ");
				fibonacci=fibonacci+antfibonacci;
				antfibonacci=fibonacci-antfibonacci;
			}
		}while(fibonacci<100);
	}
}

ViniGodoy 23 de dez. de 2012

Por favor, evite ressuscitar tópicos. Especialmente os já respondidos. Sua resposta é até mais rebuscada do que as apresentadas nesse mesmo tópico.

gledsonvc 26 de dez. de 2012

Por favor, evite ressuscitar tópicos. Especialmente os já respondidos. Sua resposta é até mais rebuscada do que as apresentadas nesse mesmo tópico.
ops, não vi que a própria pessoa que abriu o topco já tinha achado a solução com o for adaptado

thalesasaraujo 21 de mar. de 2014

O meu código ficou assim:

class Desafio{

public static void main(String[] args){

int x=0,y=1;

while(x<100){

System.out.print(x+" - ");

y += x;

x = y - x;

}

System.out.print(x);

}

}

blayd2015 24 de mar. de 2014

um exemplo bem simples para se resolver isso é assim:

public static void main(String[] args) {        
        int fibo[] = new int[20];
        int fibo02[] = new int[20];
        int i;
        
        for(i= 1; i < 20; i++){
            fibo02[i] = i;
        }
        fibo[1] = 1;
        fibo[2] = 1;
        System.out.println("Fibonacci de: "+fibo02[1]+" é: "+ fibo[1]);
        System.out.println("Fibonacci de: "+fibo02[2]+" é: "+ fibo[2]);
        
        for(i = 1; i < 18; i++){
            fibo[i+2] = fibo[i]+fibo[i+1];
            System.out.println("Fibonacci de: "+fibo02[i+2]+ " é: "+fibo[i+2]);
        }
}

espero ter ajudado...vlw

Delink 7 de out. de 2014

Sou novato no Java, mas depois de pensar um pouco acredito que consegui resolver com duas var assim:

public class fionacci_duas_var {

public static void main(String[] args) {

int prim = 0;

int seg = 1;

while ( prim < 100){

System.out.println(prim);

seg += prim;

prim = seg - prim;

}

}

}

Criado 18 de setembro de 2008

Ultima resposta 7 de out. de 2014

Respostas 31

Participantes 18

31 Respostas

Topicos relacionados