Reverse Fibonacci Series

fibonacci_sequenceEarlier today I was looking at a challenge. The problem was stated as:

“Print in reverse order a Fibonacci series”.

I have learned and used a couple times the Fibonacci series but time goes by and I am a firm believer that one should not memorize what you can look up. Software developers would look up the definition or better yet, a Class and associated method that would generate it.

Let’s start with a definition of what a Fibonacci series is from Wikipedia:

The Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Often, especially in modern usage, the sequence is extended by one more initial term:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

The challenge should specify the number of elements to display in the series since it is an infinite one. We could rephrase the challenge as:

“Print in reverse order the first N numbers in the Fibonacci series”.

The pseudo code would look as follows:

// **** generate the first N numbers of the Fibonacci series ****

int[] fib = Fibonacci(0, 1, N);

// **** reverse the order and print ****

reversePrint(fib);

Let’s take a look at the output from the console of the Eclipse IDE for my solution:

After some thought following is the test implementation:

package john.canessa.series;

import java.util.Scanner;

public class Solution {

public static void main(String[] args) throws Exception {

final int MAX_ELEMENTS            = 17;

final int FIRST_ELEMENT    = 0;

final int SECOND_ELEMENT   = 1;

// **** get the number of elements in the series ****

Scanner sc = new Scanner(System.in);

System.out.print(“main >>> maxElements: “);

int n = sc.nextInt();

sc.close();

if ((n < 2) || (n > MAX_ELEMENTS)) {

throw new Exception(“unexpected maxElements: ” + n);

}

System.out.println(“main <<< maxElements: ” + n);

// **** generate the Fibonacci series ****

Fibonacci fib        = new Fibonacci();

int[] series = fib.fibonacci(FIRST_ELEMENT,  SECOND_ELEMENT, n);

// **** reverse the Fibonacci series ****

series = fib.reverse(series);

// **** display the Fibonacci series in reverse order ****

fib.show(series);

}

}

Following is a screen capture of the Eclipse IDE console:

main >>> maxElements: 13

main <<< maxElements: 13

show <<< fib: 144 89 55 34 21 13 8 5 3 2 1 1 0

The implementation of the Fibonacci class follows:

package john.canessa.series;

public class Fibonacci {

/*

* constructor

*/

public Fibonacci() {

}

/*

* generate series

*/

public int[] fibonacci(int first, int second, int n) throws Exception {

if (n < 2) {

throw new Exception(“fibonacci <<< n: ” + n + ” < 2″);

}

int[] fib     = new int[n];

fib[0]               = first;

fib[1]               = second;

if (n <= 2) {

return fib;

}

for (int i = 2; i < n; i++){

fib[i] = fib[i – 1] + fib[i – 2];

}

return fib;

}

/*

* reverse

*/

public int[] reverse(int[] fib) {

if (fib.length <= 1) {

return fib;

}

int t = 0;

int b = fib.length – 1;

do     {

int temp      = fib[t];

fib[t]        = fib[b];

fib[b]        = temp;

t++;

b–;

} while ((t + 1) <= b);

return fib;

}

/*

* show

*/

public void show(int[] fib) {

System.out.print(“show <<< fib: “);

for (int i = 0; i < fib.length; i++) {

System.out.print(fib[i] + ” “);

}

System.out.println();

}

}

If you have comments or questions regarding this post or any other post in this blog, please do not hesitate and send me an email message.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *