# Fibonacci numbers

Jeremy King

Greenhorn

Posts: 5

posted 8 years ago

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.

/**

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.

posted 8 years ago

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.

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

posted 8 years ago

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?

posted 8 years ago

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

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

Marshal

Posts: 52581

119

posted 8 years ago

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

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

posted 8 years ago

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.

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 thereisin 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.

Each of their nuggets of wisdom contracted to a sound bite: Joshua Bloch: *Write Lots of Code*; Chet Haase: *Don't Put Your Entire Application in One Method*; Masood Mortazavi: *Start Simple and Keep Learning*; Cay Horstmann: *First, Don't Panic*

Jeremy King

Greenhorn

Posts: 5

Campbell Ritchie

Marshal

Posts: 52581

119

Marky Vasconcellos

Ranch Hand

Posts: 36

posted 8 years ago

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.

I'm brazilian and read it something about 3 years ago.. and i dont remember everything very well.

*Write Lots of Code*; Chet Haase: *Don't Put Your Entire Application in One Method*; Masood Mortazavi: *Start Simple and Keep Learning*; Cay Horstmann: *First, Don't Panic*

Campbell Ritchie

Marshal

Posts: 52581

119

Jeremy King

Greenhorn

Posts: 5

posted 8 years ago

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.

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

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

Marshal

Posts: 52581

119

posted 8 years ago

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!

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!

Campbell Ritchie

Marshal

Posts: 52581

119

posted 8 years ago

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.

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.

posted 8 years ago

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

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

Marshal

Posts: 52581

119

posted 8 years ago

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.

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.

posted 8 years ago

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).

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Campbell Ritchie

Marshal

Posts: 52581

119

posted 8 years ago

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

Let's walk before we can run; the logarithmic method is much harder to write.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).

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

posted 8 years ago

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

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

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions