2

Tenho esse enunciado em mãos:

Dada a sequência de Fibonacci 1 1 2 3 5 8 13 ... n, escreva um algoritmo para gerar a sequência até o enésimo termo, o qual deverá ser fornecido pelo usuário. Por exemplo, se o usuário digitou o número 40, deverão ser gerados 40 números.

Minha conclusão foi essa:

public class ex10 {
public static void main(String[] args) {
    Scanner x = new Scanner(System.in);
    System.out.println("Digite a quantidade de termos");
    int qtd = x.nextInt();
    int n1 = 1;
    int n2 = 1;
    System.out.print("1 ");
    System.out.print("1 ");
    qtd = qtd - 2;
    while (qtd > 0) {
        System.out.print((n1+n2) + " ");
        int n3 = n1+n2;
        n1 = n2;
        n2 = n3;
        qtd--;
    }
    System.out.println("Fim");
}

}

Tem uma solução melhor para esse algoritmo?

1
  • Seu programa só não funciona perfeito quando se pede "1", pois ele retornaria dois números. De resto, está perfeito Commented 9/06/2017 às 11:05

6 Respostas 6

8

Melhor é relativo. Se não der critérios fica difícil dizer o que é melhor. Eu fiz mais curto, ligeiramente mais eficiente e resolvi alguns problemas.

Achei um for mais adequado que um while. Se não podia, favor informar, mas é fácil separar a atribuição e incremento voltando ao while.

O primeiro termo de Fibonacci costuma ser 0 e não 1. É possível começar por outro. Se não podia é fácil trocar para 1, favor informar.

Não tem porque tratar como exceções os dois primeiros termos, deixe o algoritmo tratar tudo igual que funciona. Esta é a melhor simplificação porque dá inclusive mais legibilidade.

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner x = new Scanner(System.in);
        System.out.println("Digite a quantidade de termos");
        int n1 = 0, n2 = 1;
        for (int qtd = x.nextInt(); qtd > 0; qtd--) {
            System.out.print(n1 + " ");
            int n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        System.out.println("Fim");
    }
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

Na resposta do Antonio Alexandre tem uma boa dica de usar long para caber mais termos. Mas se é para tomar esse cuidado então um BigInteger será melhor, o long estouraria logo.

Precisa dar mais confiabilidade? Ou seja, precisa validar a entrada de dados? Em exercícios geralmente isto não é tão importante. E o que não pode? Pode digitar valores valores menores que 2? Funciona mesmo que aceite negativos, mas é o desejado. Tem um limite máximo? Se usar int ou long seria bom ter um limite superior para não deixar estourar a capacidade de armazenamento da variável. O que não funcionará é se digitar algo que não é um valor. Em Java o pessoal costuma deixar dar o erro e capturar uma exceção, pior capturam Exception que é a pior exceção para se capturar. Eu prefiro tratar isto de forma direta, mas a linguagem não ajuda muito.

Quer separar com vírgula? Aí precisa fazer exceção para o (só) primeiro termo. E aí tem que excepcionar também de acordo com a quantidade de termos digitada.

Favor avisar se quer alguma coisa diferente.

1
5

Não diria que minha solução é melhor, é apenas diferente e com uns detalhes a mais, sendo um detalhe numérico e duas firúlas estéticas, mas no algoritmo mesmo é muito parecido.

import java.util.Scanner;

public class Fibonacci
{
    public static void main(String[] args)
    {
        int tamanho = getTotalTermos();
        long[] numeros = new long[tamanho];

        numeros[0]=0;
        numeros[1]=1;

        System.out.print("0, 1");

        for(int i=2; i<numeros.length; i++)
        {
          numeros[i] = numeros[i-1] + numeros[i-2];  

          System.out.print(", " + numeros[i]);
        }

        System.out.println();
    }  

    private static int getTotalTermos()
    {
        int total_termos;
        Scanner input = new Scanner(System.in); 

        try 
        {
            System.out.print("Digite a quantidade de termos: " ); 
            total_termos = input.nextInt();

            if(total_termos<2)
            {
                 System.out.println("Por favor digite um número que seja maior do que 1" );
                 return getTotalTermos();
            } 
        }
        catch(Exception e)
        {
            System.out.println("Erro - Número inteiro inválido");
            return getTotalTermos();
        } 

        return total_termos;
    }
}
// Digite a quantidade de termos: 15
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

Detalhes a mais:

1) Tratei a digitação de caracteres que não fossem números pedindo novamente pra digitar um número válido, mas isso foi firúla.

2) Agora um detalhe que você pode ter deixado passar batido foi usar int. No meu caso usei long. Por quê? - Por que a sequência de Fibonacci cresce muito rapidamente e estoura o range numérico de int que vai de -2147483648 a + 2147483647

3) Coloquei uma vírgula separando os números. Outra firúla. :)

4) No final do meu algoritmo existirá um array numeros com a sequência de Fibonacci que poderia ser usado para alguma outra coisa.

byte = 1 byte - 8 bits = -128-127 - números inteiros

short = 2 bytes - 16 bits = -32768 a +32767 - números inteiros

int = 4 bytes - 32 bits = -2147483648 a + 2147483647 - números inteiros

long = 8 bytes - 64 bits = -922337203685477808 a 922337203685477807 - números inteiros

float = 4 bytes - 32 bits = aproximadamente 3.40282347E+38 = Ponto flutuante

double = 8bytes - 64 bits = 1.79769313486231570W+308 = Ponto Flutuante

chart = Caracteres Unicode 16 bits = 0 a 65536 = caracteres

boolean = Possuem valores true e false = booleano

Testei os nossos códigos com 78 termos e veja a diferença (use scroll e vá até o final):

ex10

Digite a quantidade de termos
78
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 -1323752223 512559680 -811192543 -298632863 -1109825406 -1408458269 1776683621 368225352 2144908973 -1781832971 363076002 -1418756969 -1055680967 1820529360 764848393 -1709589543 -944741150 1640636603 695895453 -1958435240 -1262539787 1073992269 -188547518 885444751 696897233 1582341984 -2015728079 -433386095 1845853122 1412467027 -1036647147 375819880 Fim
CONSTRUÍDO COM SUCESSO (tempo total: 3 segundos)

meu Fibonacci

Digite a quantidade de termos: 78
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757
CONSTRUÍDO COM SUCESSO (tempo total: 3 segundos)
1
  • 1
    Exemplo de uso futuro do array: Se o problema fosse rodar diversas vezes, o seu código está pronto para memoização do resultado, assim não precisaria recalcular um resultado já obtido Commented 9/06/2017 às 11:04
2

Utilizando Java 8 existe uma forma bem prática de resolver, você pode utilizar um UnaryOperator para representar uma operação que será aplicada dentro do iterate do stream, apos isto basta implementar seu Consumer, basicamente é onde o resultado do operator irá implicar se utilizar o forEach, segue abaixo a implementação

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    System.out.println("Digite a quantidade de termos");
    int quantidade = sc.nextInt();

    UnaryOperator<Long[]> operator = p -> new Long[] { p[1], p[0] + p[1] };
    Consumer<Long[]> consumer = p -> System.out.print(p[0] + " ");

    Stream.iterate(new Long[] { 1L, 1L }, operator)
        .limit(quantidade)
        .forEach(consumer);

    System.out.println("\nFim");
}

Agora se você quiser guardar os resultados você precisa trocar de forEach para map e trocar a implementação de Consumer para Function além de ao fim usar o Collector para recuperar estes dados do processador. Segue abaixo esta outra implementação:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    System.out.println("Digite a quantidade de termos");
    int quantidade = sc.nextInt();

    UnaryOperator<Long[]> operator = p -> new Long[] { p[1], p[0] + p[1] };
    Function<Long[], Long> consumer = p -> p[0];

    List<Long> resultado = Stream.iterate(new Long[] { 1L, 1L }, operator)
        .limit(quantidade)
        .map(consumer)
        .collect(Collectors.toList());

    for(Long item : resultado){
        System.out.print(item + " ");
    }

    System.out.println("\nFim");
}

Veja que com programação funcional o problema é resolvido de forma mais limpa e as operações a maioria das vezes são abstratas

1

A questão já foi respondida, mas eu vou dar uma resposta de um ponto de vista mais funcional apenas como referência.

Primeiramente, eu decidi criar uma classe para guardar uma tupla:

class Tuple<X, Y>
{
    public final X x;
    public final Y y;

    public Tuple(X x, Y y)
    {
        this.x = x;
        this.y = y;
    }

    public String toString() {
        return ("(" + x + ", " + y + ")");
    }
}

Agora, vamos usar o conceito de sequência infinita, ou, no mundo Java, Stream. Vamos usar o conceito de geradores. O gerador é implementado pela função interate da classe Stream:

Stream<Tuple<Integer, Integer>> fiboStream =
        Stream.iterate(
                new Tuple<>(1,1),
                t -> new Tuple<>(t.y, t.x + t.y));

O valor inicial é a Tupla (1,1). A próxima é calculado por (y, x + y). Vamos pegar o fibonacci de 10:

fiboStream.
    limit(10).
    reduce((fst, snd) -> snd).
    get().x
-2

public class Program {

public static void main(String[] args) {

    Stream<Long> limit = Stream.iterate(new Long[] { 0L, 1L }, par -> new Long[] { par[1], par[0] + par[1] })
            .map(par -> par[0]).limit(10);

    System.out.println(Arrays.toString(limit.toArray()));

}

}

1
  • 1
    Bem vindo ao Stack Overflow em Português. Esse código pode ser uma solução para a pergunta, mas sua resposta pode ser melhor se você incluir uma explicação sobre os principais pontos do código. O objetivo não é ajudar apenas quem fez a pergunta, mas os próximos visitantes também. Leia mais em Respostas apenas com código - O que fazer?. Commented 4/10/2020 às 0:50
-4

Em Golang pode ser feito assim:

func gerador_fibonacci() chan int {
  c := make(chan int)

  go func() { 
    for i, j := 0, 1; ; i, j = i+j,i {
        c <- i
    }
  }()

  return c
}

func main() {
    c := gerador_fibonacci()
    for n := 0; n < 12 ; n++ {
        fmt.Println(<- c)
    }
}

Ou assim:

package main

    import "fmt"

    func fib(n uint) uint {
        if n == 0 {
            return 0
        } else if n == 1 {
            return 1
        } else {
            return fib(n-1) + fib(n-2)
        }
    }

    func main() {
        n := uint(10)
        fmt.Println(fib(n))
    }
1
  • 4
    A pergunta tem uma tag Java, não Go, está resposta é inútil neste contexto. Veja o tour, e a central de ajuda. Várias de suas respostas estão apresentando problemas, recebendo sinalizações e o sistema vai acabar bloqueando de continuar respondendo até resolver os problemas. Evite que isto aconteça.
    – Maniero
    Commented 9/06/2017 às 11:28

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .