Monday, October 5, 2009

Program to Display the First N Values of the Fibonacci Sequence


Problem: "In mathematics, there is a famous sequence of numbers called the Fibonacci sequence, after the thirteenth-century Italian mathematician Leonardo Fibonacci. The first two terms in this sequence are 0 and 1, and every subsequent term is the sum of the preceding two. Thus the first several terms in the Fibonacci sequence are as follows:

fib0 = 0
fib1 = 1
fib2 = 1 (0+1)
fib3 = 2 (1+1)
fib4 = 3 (1+2)
fib5 = 5 (2+3)
fib6 = 8 (3+5)

Write a program to display the values in this sequence from fib0 through fib15" (Roberts Ch 4, Exercise 9).

Program from PrettyPrinter.de: (thanks for the tip, Arnab! no more screenshots of Eclipse)


/*
* File: FibSequence.java
* Name: Renee
* Section Leader: Me!
* -----------------
* This program displays the first N numbers in the Fib sequence (the user can pick how
* far N is by changing the private constant "END.") It first sets the sequence in motion
* by explicitly defining and printing out fib0 and fib1, but henceforth builds off
* the prior numbers of the sequence by re-setting the values of n2, n1, and n0 for every
* loop in the program.
*/


import acm.program.*;


public class FibSequence extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
println(n1);

//Now kicking off the fun part.
for (int i = 2; i < END; i++) {
int n2 = n1 + n0;
println(n2);
n0=n1;
n1=n2;

}
}

//Private constant; "End" is the the nth number in the Fib sequence displayed.

private static final double END = 15;
}



What the output looks like:




What made it tough: There are some things you learn in Java that completely fly in the face of what you learned in math class. For example, if you have the decimal number (or, "double") 2.9, but you want it to be converted into an integer, it would be converted to 2. Not 3! Everything after the integer gets truncated, even if it's not the closest integer! Similarly, if your program is working in integers, and you divide 15 by 4, the number is displayed as 3! No decimal points allowed.

The other practice that I'm struggling with is that of re-declaring variables. In one program, n can equal 1, and later on in the program, n equals 2. N just changes as your program moves along if you want it to!

If that weren't anti-instinctive enough, this Fib program gets solved declaring a variable to equal another variable, but then changing those assignments around. You find the number in a Fib sequence by summing the two outputs of the sequence that came before it (ie, Fib(n)=Fib(n-1)+Fib(n-2)), but since I can't do functions in Java yet, I store the values of the past functions by reassigning the variables down the chain.

If you look at the "fun part," once we print n2 (the latest number in the sequence to be calculated), we move the value of n2 down to the variable n1, and move the value of n1 down to the variable n0, and then we use the new n1 and n0 to calculate the new n2.

Time to completion: 3 hours.

Lingering questions: I don't like that I started off explicitly writing fib(0) and fib(1) before I could start the elegant part of the code. Is there a way to do this without?

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. In short -- nope, not until you're taught how to write your own functions ("methods"). Without that, it's the initial values that determine how the entire sequence progresses, and you definitely need to explicitly set them.

    In the meantime, you can indeed make your current code slightly more elegant by changing it to use only two variables instead of three.. although it is an unnecessary modification that comes at the cost of losing some clarity. Anyway, I'll leave that as an exercise to the reader, though lemme know if you still want to know despite my warnings. :]

    ReplyDelete
  3. Also, your code only prints f0 through f14. You need to make END be 16, or change your condition to be a <=.

    I also don't know enough java to tell what else you could of done to make it more efficient(or what you have learned in the book yet).

    ReplyDelete
  4. I don't see why you feel the initialization is inelegant. The two starting values of the Fibonacci sequence are defined as such... And iterative algorithm has three main parts: initializiation, loop code, stop condition. Using a method would compartimentalize it a bit better, but you would still have to initialize these two values explicitly.

    I'd only dock a few style points from your code due to lack of indentation ;-).

    ReplyDelete