aspose file tools*
The moose likes Beginning Java and the fly likes Fibonacci numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Fibonacci numbers" Watch "Fibonacci numbers" New topic
Author

Fibonacci numbers

Jeremy King
Greenhorn

Joined: May 27, 2008
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

Joined: Jan 01, 2009
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

Joined: Aug 16, 2005
Posts: 13875
    
  10

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.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Jeremy King
Greenhorn

Joined: May 27, 2008
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
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36501
    
  16
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

Joined: Jan 28, 2009
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.


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

Joined: May 27, 2008
Posts: 5
Um, okay? Thanks for all the suggestions, I guess. I'll figure it out eventually.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36501
    
  16
[Pedantic mode] It's "unus" in Latin: "uno" would be Spanish or Italian. [/pedantic mode]
Marky Vasconcellos
Ranch Hand

Joined: Jan 28, 2009
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

Joined: Oct 13, 2005
Posts: 36501
    
  16
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

Joined: May 27, 2008
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
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

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

Joined: Oct 13, 2005
Posts: 36501
    
  16
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
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39


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

Joined: Oct 13, 2005
Posts: 36501
    
  16
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
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

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

Joined: Oct 13, 2005
Posts: 36501
    
  16
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

Joined: Oct 27, 2005
Posts: 19543
    
  16

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
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 36501
    
  16
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

Joined: Oct 27, 2005
Posts: 19543
    
  16

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

Joined: Oct 13, 2005
Posts: 36501
    
  16
You have seen Kaldewaij and I have seen Kaldewaij. It's probably not that well-known!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Fibonacci numbers
 
Similar Threads
help with program
Fibonacci numbers problem
Code Help
How to write an algorithm for an average of values?
Using Nested For Loops To Make Triangle