Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Fibonacci numbers

Jeremy King
Greenhorn
Posts: 5
import java.util.Scanner;

/**
Computes the amount of green crud after a given number of days and a
given starting amount.
*/
public class GreenCrud {

public static void main(String[] args) {
// Make a Scanner to read data from the console
Scanner console = new Scanner(System.in);

// Read in the initial size of the crud population
System.out.println(
"Enter initial green crud population size (in pounds), ");
System.out.println("or a blank line to quit:");
String size = console.nextLine();

// Stop on blank line
while ((size != null) && (size.length() > 0)) {
double initialSize = Double.parseDouble(size);

// Read in the number of days
System.out.println("Enter the number of (whole) days:");
int days = console.nextInt();

// --------------------------------
// ----- ENTER YOUR CODE HERE -----
// --------------------------------
double fi = 0;
for (int i=5; i==5; i++)
fi = initialSize + fi;
System.out.println("The size (in pounds) of the green crud population is: "+ fi);

// --------------------------------
// --------- END USER CODE --------
// --------------------------------

// Start again, giving the user a chance to cancel by entering
// a blank line.
System.out.println();
System.out.println(
"Enter initial green crud population size (in pounds), ");
System.out.println("or a blank line to quit:");

// Skip over the end-of-line for the last number the user entered
console.nextLine();
size = console.nextLine();
}

}

}
The formula applies most straightforwardly to asexual reproduction at a rate of one offspring per time period. In any event, the green crud population grows at this rate and has a time period of five days. Hence, if a green crud population starts out as 10 pounds of crud, then in five days there is still 10 pounds of crud; in ten days there is 20 pounds of crud, in fifteen days 30 pounds, in twenty days 50 pounds, and so forth. Write a program that takes both the initial size of a green crud population (in pounds) and a number of days as input, and outputs the number of pounds of green crud after that many days. Assume that the population size is the same for four days and then increases every fifth day. Your program should allow the user to repeat this calculation as often as desired.

The red is what I have written so far and it isn't working the way it should. I know the problem is in the for loop, but not quite sure where. Should the initialization be the number of days input by the user? or should that be the second part of the loop? and I don't think the loop body is quite right but I'm stumped and about to lose my mind. Any help or suggestion would be greatly appreciated.

Balu Sadhasivam
Ranch Hand
Posts: 874
Jeremy ,
those 2 variables that is given as input can be used

The logic is similar to above , i hvnt tried to work out the code

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15284
39
for (int i=5; i==5; i++)

Do you understand what this line means exactly?

It means: "Start by setting i to 5. Execute the body of the loop as long as i is equal to 5. Increment i after each iteration."

This will run the body of the loop only once - because after the first iteration, i will be incremented to 6, so that i == 5 is not true anymore.

Jeremy King
Greenhorn
Posts: 5
I understand that, now I'm thinking that the loop should be based on the days? And the loop body should be increasing the amount of the green crud. But it only increases every 5th day, so every 5th day the new amount of crud would be the current amount plus the last amount, or am I wrong? So something like for ( ? ; i <= days; i += 5) I'm not sure what to initialize to, or if the for statement is even close. and the body would be in need of new variables to increase the amount?

Henry Wong
author
Marshal
Posts: 21122
78
So something like for ( ? ; i <= days; i += 5) I'm not sure what to initialize to, or if the for statement is even close. and the body would be in need of new variables to increase the amount?

Well, since you have a "<=" comparison, your init should probably be "int i = 1".

As for "if the for statement is even close", that would depend on what's in the body. Try it... you can always change the looping structure later, if you can't get it to work.

Henry

Campbell Ritchie
Sheriff
Posts: 48968
60
I would also suggest you implement a Fibonacci numbers class or method, which calculates Fibonacci numbers incrementing 1 at a time. When you have got that to work, you can enhance it to work with steps of 5.

By the way: most people think there is no 0-th member of the classic Fibonacci series, but you can use fib(0) = 0 is you wish. Use fib(1) = 1 and fib(2) = 1 and you should get fib(10) = 55.

And now half the Ranch will turn up and say there is in fact a 0-th member to the series!

Marky Vasconcellos
Ranch Hand
Posts: 36
Campbell Ritchie wrote:I would also suggest you implement a Fibonacci numbers class or method, which calculates Fibonacci numbers incrementing 1 at a time. When you have got that to work, you can enhance it to work with steps of 5.

By the way: most people think there is no 0-th member of the classic Fibonacci series, but you can use fib(0) = 0 is you wish. Use fib(1) = 1 and fib(2) = 1 and you should get fib(10) = 55.

And now half the Ranch will turn up and say there is in fact a 0-th member to the series!

Following the ideia of some mathematics who believes the universe are just numbers.

The zero of the fibonacci sequence are the nothing
The first one is the begin, the 'Uno' latin word to one.
And the rest of numbers make the respiration of earth. i dont want explain it right now xD but if someone is curios just ask.

Jeremy King
Greenhorn
Posts: 5
Um, okay? Thanks for all the suggestions, I guess. I'll figure it out eventually.

Campbell Ritchie
Sheriff
Posts: 48968
60
[Pedantic mode] It's "unus" in Latin: "uno" would be Spanish or Italian. [/pedantic mode]

Marky Vasconcellos
Ranch Hand
Posts: 36
Sorry.. it's really Unus the 1... and Uno is directly derived from the latin Unus.
I'm brazilian and read it something about 3 years ago.. and i dont remember everything very well.

Campbell Ritchie
Sheriff
Posts: 48968
60
Jeremy King wrote:Um, okay? Thanks for all the suggestions, I guess. I'll figure it out eventually.
Does that include all suggestions or only the useful ones?

Have you got anything working yet?

Jeremy King
Greenhorn
Posts: 5
I couldn't really get anything working. I was more referring to how the discussion moved into a debate about zero being a number and then something about the existence of the universe.

Henry Wong
author
Marshal
Posts: 21122
78
I couldn't really get anything working.

Why didn't you just say so earlier? Anyway, here is another hint....

A fib value is dependent on the previous two fib values -- so you need to keep track of two interim fib numbers, in that loop, as you are calculating the targeted fib number.

I was more referring to how the discussion moved into a debate about zero being a number and then something about the existence of the universe.

Interestingly, it didn't really move too much off topic. That part of the discussion was to help you figure out what the two starting fib numbers are supposed to be -- or else, you won't be able to start your loop.

Henry

Campbell Ritchie
Sheriff
Posts: 48968
60
Beware: There are several ways of calculating Fibonacci sequences. The obvious recursive way runs in quadratic time, so you need to work out one of the more complicated methods which run in linear time.

There is a method which runs in logarithmic time, which you can find in Kaldewaij's book (page 98-99 if I remember correctly) which I have a copy of somewhere, but that will be too complicated for you!

Henry Wong
author
Marshal
Posts: 21122
78

Since (and I am guessing), the instructor mentioned to use a loop, I think that it is safe to assume that the instructor is assuming that the solution will be the basic brute force approach... Just start from fib-0, or fib-1, and work your way up.

Henry

Campbell Ritchie
Sheriff
Posts: 48968
60
If you start with fib(1) [=1] and fib(2) [=1] then you can increment both numbers in a loop. That runs in linear time, so I think "brute force" is a bit of an exaggeration, Henry!
Remember, starting like that you should get fib(10) = 55; if you get 34 or 89 you have got an out-by-one error somewhere. If you get 88 or 90 or 34 your arithmetic has gone wrong.

Henry Wong
author
Marshal
Posts: 21122
78
That runs in linear time, so I think "brute force" is a bit of an exaggeration, Henry!

Okay, maybe "brute force" is the wrong word. Hmmm.... I don't know what should be the right word... "straightforward", "first choice", "obvious".... nothing really describes it perfectly.

The fib solution is an interesting solution, as the recursive solution is a "good" learning tool, and people have been trying to inprove it, even thoough the "straightforward obvious" solution is much better. There are not many problems that have a commonly used recursive solution, and yet, have a better iterative solution.

Henry

Campbell Ritchie
Sheriff
Posts: 48968
60
You can pass one argument to a recursive Fibonacci method, in which case it goes into exponential time: O(1.618^n) time, in fact. I shall allow the reader to work out where the 1.618 comes from.

If you start passing two arguments, one being a previous Fibonacci number, you can get it to run in linear complexity. I remember writing lots of Fibonacci methods and functions for Programming Paradigms in Autumn '07. But I can't remember just at the moment how I did it.

Rob Spoor
Sheriff
Posts: 20531
54
Fibonacci can also be performed in logarithmic time (using the Matrix form in the link), and by approximation even in constant time (using the closed form expression).

Campbell Ritchie
Sheriff
Posts: 48968
60
Rob Prime wrote:Fibonacci can also be performed in logarithmic time (using the Matrix form in the link), and by approximation even in constant time (using the closed form expression).
Let's walk before we can run; the logarithmic method is much harder to write.

And surely you should be quoting Kaldewaij's book. Page 98-99 if I remember correctly

Rob Spoor
Sheriff
Posts: 20531
54
That's where I got my implementation from alright, but I didn't know the book was so well-known.

But you're right, Fibonacci should be implemented in three steps:
- recursive, because that's logically speaking the easiest
- linear, just to speed it up
- logarithmic, to speed it up some more

Campbell Ritchie
Sheriff
Posts: 48968
60
You have seen Kaldewaij and I have seen Kaldewaij. It's probably not that well-known!