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 number is from Wikipedia:

The Fibonacci numbers are 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:

main >>> maxElements: 7
main <<< maxElements: 7
show <<< fib: 8 5 3 2 1 1 0 main >>> maxElements: 17
main <<< maxElements: 17
show <<< fib: 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0 

After some thought following is the test implementation:

package john.canessa.series;

import java.util.Scanner;

/*
 * 
 */
public class Solution {

	// **** testing scaffold ****
	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 another screen capture from 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 series ****
	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 series ****
	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, or if you need technical or management assistance in any phase of the SDLC  of a project, please do not hesitate and leave me a message below. Requests for help will not be made public.

John

Twitter:  @john_canessa

2 thoughts on “Reverse Fibonacci Series”

  1. Hello Mr. Canessa,
    I have a long fixed rectangle in my front yard and I would like to design a fibonacci garden within this rectangle. The width of the rectangle is 11.5 feet. The length is 48.5 feet. I am thinking I could fit two fibonacci designs within this but I don’t know where to start with my measurements. How do I go from an 11.5 x 11.5 big square to the smaller squares and rectangles? Any help will be appreciated. I do sort of understand but would like some help so that it looks right.
    Thank you!
    Regina

    1. Hello Regina,

      Thanks for the message.
      Please address me using my first name.

      Decided to update the looks of this post.
      The code was not that easy to follow.
      Hopefully the current format is better.

      I decided to reply using a post in this blog.
      The name is “Yard Design”.

      Regards;

      John

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.