Simple solution for Fibonacci algorithm

2

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 up to the nth term, which should be provided by the user. For example, if the user 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");
}

}

Do you have a better solution for this algorithm?

    
asked by anonymous 09.06.2017 / 05:46

5 answers

7

Better is relative. If it does not give criteria it is difficult to say which is better. I made it shorter, slightly more efficient and solved some problems.

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

The first Fibonacci term is usually 0 and not 1. It is possible to start with another. If it could not be easy to change to 1, please inform.

You do not have to treat the first two terms as exceptions, letting the algorithm treat everything just as it works. This is the best simplification because it gives even more readability.

import java.util.*;

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

See running on ideone . And no Coding Ground . Also put it in GitHub for future reference .

Antonio Alexandre's answer has a good hint of using long to fit more terms. But if it is to take such care then BigInteger will be better, long would pop out soon.

Need to give more reliability? In other words, do you need to validate the data entry? IN exercises usually this is not so important. And what can not? Can you enter values less than 2? It works even if it accepts negatives, but is what you want. Do you have a ceiling? If you use int or long it would be nice to have an upper limit to not let the storage capacity of the variable pop. What will not work is if you enter something that is not a value. In Java, people usually let the error and catch an exception, worse capture Exception which is the worst exception to capture. I prefer to handle this directly, but the language does not help much.

Want to separate with comma? There you must make exception for the (only) first term. And there you have to also excepte according to the amount of terms typed.

Please let me know if you want anything different.

    
09.06.2017 / 14:07
4

I would not say that my solution is better, it's just different and with a few more details, being a numerical detail and two aesthetic firulas, but in the same algorithm it's 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 tried to enter characters other than numbers by asking again to enter a valid number, but that was firula.

2) Now one detail that you may have let pass beaten was to use int. In my case I used long. Because? - Why does the Fibonacci sequence grow very rapidly and bursts the num numeric range of int ranging from -2147483648 to + 2147483647

3) I placed a comma separating the numbers. Another firm. :)

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 to + 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 = They have true and false values = Boolean

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)
    
09.06.2017 / 06:37
1

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

First, I decided to create a class to save 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 interate function of the Stream class:

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

The initial value is Tuplet (1,1). The next one is calculated by (y, x + y). Let's get the fibonacci of 10:

fiboStream.
    limit(10).
    reduce((fst, snd) -> snd).
    get().x
    
09.06.2017 / 15:09
1

Using Java 8 is a very practical way to solve, you can use UnaryOperator to represent an operation that will be applied within iterate of stream , after this you just have to implement your Consumer , basically this is where the result of the operator will imply if you use forEach , it 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 from forEach to map and change the implementation from Consumer to Function and finally use Collector to retrieve this data from the processor. Here is another 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");
}

See that with functional programming the problem is resolved more cleanly and operations are most often abstract

    
09.06.2017 / 16:04
-2
  

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))
    }
    
09.06.2017 / 08:55