Simple Solution for Fibonacci Algorithm

Question

I have this statement in hand:

Given the Fibonacci sequence 1 1 2 3 5 8 13 ... n, write an algorithm to generate the sequence to the nth term, which must be provided by the user. For example, if the user has entered the number 40, 40 numbers should be generated.

My conclusion was this:

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");
}

}

There is a better solution for this algorithm?

Answer 1

Better is relative. If you don’t give criteria it is difficult to say which is better. I did shorter, slightly more efficient and solved some problems.

I found a for more suitable than a while. If you could not, please inform, but it is easy to separate the assignment and increment back to the while.

The first term of Fibonacci is usually 0 and not 1. It is possible to start with another term. If you could not easily change to 1, please inform.

There is no reason to treat the first two terms as exceptions, let the algorithm treat everything the same as it works. This is the best simplification because it gives even more readability.

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");
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

In the reply of Antonio Alexandre has a good tip to use long to fit more terms. But if it is to take that care then one BigInteger it will be better, the long blow up right away.

Need to give more reliability? IE, need to validate data entry? EM exercises is usually not so important. And what can not? Can you enter values smaller than 2? It works even if you accept negatives, but it is what you want. Do you have a maximum limit? If you use int or long it would be nice to have an upper limit so as not to let the variable’s storage capacity burst. What will not work is if you type something that is not a value. In Java people usually let you give the error and catch an exception, worse they capture Exception which is the worst exception to capture. I prefer to treat this directly, but the language doesn’t help much.

Want to separate with a comma? Then you need to make an exception for the (only) first term. And there you have to exception also according to the amount of terms entered.

Please let us know if you want something different.

Answer 2

I would not say that my solution is better, is just different and with a few more details, being a numerical detail and two aesthetic firulias, but in the same algorithm is very similar.

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

More details:

1) I treated the typing of characters that were not numbers asking again to enter a valid number, but this was a violation.

2) Now one detail you may have missed was using int. In my case I used long. Why? - Why the Fibonacci sequence grows very fast and bursts the numerical range of int from -2147483648 to + 2147483647

3) I put a comma separating the numbers. Another thread. :)

4) At the end of my algorithm there will be an array of numbers with the Fibonacci sequence that could be used for something else.

byte = 1 byte - 8 bits = -128-127 - integers

short = 2 bytes - 16 bits = -32768 to +32767 - integers

int = 4 bytes - 32 bits = -2147483648 a + 2147483647 - integers

long = 8 bytes - 64 bits = -922337203685477808 to 922337203685477807 - integers

float = 4 bytes - 32 bits = approximately 3.40282347E+38 = Floating point

double = 8bytes - 64 bits = 1.79769313486231570W+308 = Floating Point

Chart = 16-bit Unicode characters = 0 to 65536 = characters

Boolean = Have true and false = boolean values

I tested our codes with 78 terms and see the difference (use scroll and go to the end):

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)

my 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)

Answer 3

The question has already been answered, but I will give an answer from a more functional point of view just as reference.

First, I decided to create a class to hold a tuple:

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 + ")");
    }
}

Now, let’s use the concept of infinite sequence, or, in the Java world, Stream. Let’s use the concept of generators. The generator is implemented by the function interate class Stream:

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

The initial value is Tuple (1,1). The next is calculated by (y, x + y). Let’s take the Fibonacci of 10:

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

Answer 4

Using Java 8 there is a very practical way of resolving, you can use a UnaryOperator to represent an operation that will be implemented within the iterate of stream, after this just implement your Consumer, basically is where the result of Operator will imply if you use the forEach, follows below the implementation

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");
}

Now if you want to save the results you need to change forEach for map and exchange the implementation of Consumer for Function in addition to the end use the Collector to recover this processor data. Below is this other implementation:

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");
}

Note that with functional programming the problem is solved more cleanly and the operations most of the time are abstract

Answer 5

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()));

}

}

Answer 6

In Golang it can be done like this:

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)
    }
}

Or so:

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))
    }