PDA

View Full Version : java programming help (again)




phiber optik
Apr 26, 2006, 10:48 PM
hey all
well i was trying to write some code that would output the first 20 fibonacci numbers, but im having some trouble when i impliment it. whenever i try to run the program (java fibonacci 20) it gives me this error:
Exception in thread "main" java.lang.NoSuchMethodError: main
any help will be appreciated!
here's the code (its a little weird i guess im still learning the language):
import java.util.*;

public class fibonacci {

public void main (String args[]) {
int input = Integer.parseInt(args[0]);
int result = fibonacci(input);
System.out.println(result);
}

public int fibonacci(int x) {
int a;
int b;
b = 1;
while (x > 0) {
a = 0;
a = a + b;
b = a ;
System.out.println(b);
x = x - 1;

}
return 0;
}
}



jsw
Apr 26, 2006, 10:49 PM
Try changing the method signature to:

public static void main(String[] args)

phiber optik
Apr 26, 2006, 10:58 PM
well now it runs, so that helped! Now, the problem is that i get 20 1's. anyone got any ideas how to edit it to make it display 20 fibonacci numbers?

therevolution
Apr 26, 2006, 11:03 PM
Well, have you examined your logic closely?

Hint: look at the first line of your 'while' loop. You're resetting 'a' to zero every time you loop. You want to perform that initialization before the loop starts, like you did with 'b'.

phiber optik
Apr 26, 2006, 11:08 PM
yeah that could affect it :p
but im still getting the same output
hmmm.....

therevolution
Apr 26, 2006, 11:13 PM
Yeah, I was just trying to give you a starting point.

Try pretending that you are 'executing' your code and keep track of the variable names on a piece of paper. You may have to do a few loops before you see that your algorithm isn't matching up with how it should be, and you can make adjustments from there.

Sorry, I'm a meanyhead when it comes to helping people with their programming problems, because I believe you don't learn much when someone just gives you the answer. You need to learn to step through your code if you're going to be a competent programmer. Start now! :)

Doctor Q
Apr 26, 2006, 11:44 PM
Your approach to helping is perfect, therevolution.

Tell us how it goes as you make changes, phiber optik, and we'll answer questions and give tips to help.

phiber optik
Apr 26, 2006, 11:53 PM
if a = 2
while (something)
b = (a -2) + (a -1)
how do i have the program ignore a = 2 the second time around?

Doctor Q
Apr 27, 2006, 12:44 AM
You might not even need an if statement, but let's find out.

Sometimes the problem in programs like this is that you try to write the initialization code, and then the loop, because they come in that order, when it's much easier if you start by considering what the loop should do and from that determine what initialization is appropriate.

So let's think about it this way. I assume that you want your a and b variables to represent two consecutive numbers in the Fibonacci sequence. So your while loop is going to repeat a certain number of times computing one more Fibonacci number each time as a and b move through the values. Is that right?

You know the Fibonacci series: 1 1 2 3 5 8 13 21 34 55 etc. So think about a particular case. Suppose a is 5 and b is 8 and you want the code in the loop to change a and b to the next values in the sequence, namely change a to 8 and change b to 13, and to output the 8. What assignment statements and call to System.out.println would do that?

In other words:As the loop body starts: a=5 and b=8.

After the loop body ends: a=8 and b=13 and the output is 8.(If you need an extra variable to use temporarily to store a value, that's fine.)

Once you figure out the assignment and println statements to do what you want for 5 and 8, your loop code is done because the same logic should work for anywhere in the sequence.

And, once you figure that out, THEN figure out how to set a and b before the while loop to make the first Fibonacci values come out. It'll be simple. Assign some small integer value to a and some small integer value to b to make the loop start correctly, either by logic or by trial and error.

It'll be easiest to help you if you post your code. If you put and tags around it in your forum posts, it'll stay formatted correctly, e.g., public static void main (String args[]) {
int input = Integer.parseInt(args[0]);
int result = fibonacci(input);
System.out.println(result);
}

ChrisBrightwell
Apr 27, 2006, 01:17 AM
Your logic is flawed.


private static int fib(int x)
{
if (x == 0 || x == 1)
return x;

else
return fib(x-1) + fib(x-2);
}


Then your main will look something like this.


public static void main(String[] args)
{
for(int x=0; x<20; x++)
{
System.out.println("Input: " + x + ", Output: " + fib(x));
}
}

phiber optik
Apr 27, 2006, 11:03 PM
two questions:
(If you need an extra variable to use temporarily to store a value, that's fine.)
how do you do this? I simply dont have the programming vocab to know how to create a temporary value. Is it an argument for a variable?
And does the value of a become reset every time the code loops, or is the altered value retained into the next loop, ignoring the initialization out of the loop?
Thanks tons for the input!!

phiber optik
Apr 27, 2006, 11:05 PM
and here's the code i have so far: (thanks for the /code tip)
import java.util.*;

public class fibonacci {

public static void main (String args[]) {
int input = Integer.parseInt(args[0]);
int result = fibonacci(input);
System.out.println(result);
}

public static int fibonacci(int x) {
int a;
int b;
int c;
c = 0;
a = 2;
while (x > 0) {

b = (a - 1) + (a-2);

if (c < 1)
a = b;
System.out.println(b);
x = x - 1;

c = c + 1;
}
return 0;
}
}


this version simply outputs a whole bunch of -1, but i thought id give you an update. Thanks!

janey
Apr 27, 2006, 11:30 PM
I still think there's something wrong with your logic.

Maybe here's a pointer or two:

Think about what the fibonacci sequence is, and how you calculate it:
f(n) =

0 if n == 0
1 if n == 1
(n-1)+(n-2) if n > 1


Create a temp variable or two to store numbers you might need to calculate the fibonacci numbers, like int firstTempValue = 0 and int secondTempValue = 1

Then, to output the first x numbers of the fibonacci sequence, you could have an if statement for the first two numbers of the sequence (as they can't be calculated), and then have a for loop at the end of the if statement, starting from 2 (like for( int i = 2; i >= x..., where x is the number of fibonacci numbers you want), to calculate the rest of the numbers as needed.

Using the number of fibonacci numbers you want, the fact that you calculate the fibonacci numbers as stated above, and a temp variable or two to store any intermediate result, try to write down a way you can write it, and implement it.


However, just as a heads up, recursion is not the right thing to use in this situation, a la something like
private static int fibonacci ( int x ) {
if ( x == 0 || x == 1 )
return x;
else
return fibonacci(x-1)+fibonacci(x-2);
}

because there is an easier-to-understand version where you don't need to use recursion at all, and doesn't have the potential problems that go with recursion.

ChrisBrightwell
Apr 27, 2006, 11:40 PM
and here's the code i have so far: (thanks for the /code tip)... Did you look at the code I posted?

Your fibonnaci() method is doing too much. The loop should be in your main() method.

janey
Apr 27, 2006, 11:42 PM
... Did you look at the code I posted?

Your fibonnaci() method is doing too much. The loop should be in your main() method.
nothing wrong with the code you posted, but i'd love to see what it does if you want the first 20000 numbers in the sequence calculated. ;) (oh god just imagine..)

Let me expand with a similar problem you find in a lot of intro books as an example of how to use recursion, and also a big example of why not to use recursion in this particular situation: the factorial problem.

factorial using recursion

int Factorial ( int number ) {
if ( number == 1 ) {
return number;
}
else {
return number * Factorial( number - 1 );
}
}


factorial using iteration

int Factorial ( int number ) {
int intermediateValue = 1;
for ( int factor = 2; factor <= number; factor++ ) {
intermediateValue = intermediateValue * factor;
}

return intermediateValue;
}


Now, given both of those, which one would you pick?
I'd go for the second, cause it's easier to understand, and it's better than the recursive version which would be insane if you were calculating the factorial of, say, 5897923.

Recursion's an awesome tool when used appropriately (i.e. quicksort). When there's a simpler and more efficient way of solving the problem without recursion, it's most definitely not appropriate :) (Of course, you could argue that a lookup table would be more efficient, but..)

ChrisBrightwell
Apr 28, 2006, 12:08 AM
nothing wrong with the code you posted, but i'd love to see what it does if you want the first 20000 numbers in the sequence calculated. ;) (oh god just imagine..)No, I'm well aware of the problem with higher values in this situation ... but he only has to count the first 20 values.

Doctor Q
Apr 28, 2006, 01:08 AM
two questions:

how do you do this? I simply dont have the programming vocab to know how to create a temporary value. Is it an argument for a variable?
And does the value of a become reset every time the code loops, or is the altered value retained into the next loop, ignoring the initialization out of the loop?
Thanks tons for the input!!It looks like you figured out how to use temporary variables, e.g., int c ;, but I'm confused what your current plan is since my suggestion (to concentrate on one particular case to figure out the code to put in the while loop) was followed by other proposals. Should I say more about what I had in mind or are you now following another plan?

As janey says, this problem could be solved either with iteration or with recursion. For your purposes, either way would work and either way would be fine since you don't care about the tradeoff between elegance and efficiency.

janey
Apr 28, 2006, 01:14 AM
No, I'm well aware of the problem with higher values in this situation ... but he only has to count the first 20 values.
Well then, why not a

System.out.println("0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181");


:o :D :D :D
Just kidding.

Yeah, I know in this situation it's not a big deal, but looking at the way he's trying to write it, looks like he's just using it to display the first 20, but leaves room for other values (i.e. 3, 10, 50, 300..)

Doctor Q
Apr 28, 2006, 01:40 AM
Don't laugh so hard, janey. I had a problem on an exam in a programming class, to write a program that would output the English for a given dollar amount, from $0.01 to $99.99, and one student turned in something like this:if ( amount == 0.01 ) printf("One cent\n") ;
else if ( amount == 0.02 ) printf("Two cents\n") ;
...
else if ( amount == 99.99 ) printf("Ninety nine dollars and ninety nine cents\n") ;as if a compiler would fill in the "..." part for him or the professor would accept that as his program. (The professor did not.)

My answer to that exam question was a little more elegant than that. Although I didn't get a chance to make sure mine was correct, and the other student's program certainly would have been correct, once he ever finished it.

janey
Apr 28, 2006, 02:01 AM
That is SOOOOOOOOOOO wtf worthy..
http://www.thedailywtf.com/

I actually did something like that for a class:
http://applegoddess.livejournal.com/37254.html

gekko513
Apr 28, 2006, 02:20 AM
and here's the code i have so far: (thanks for the /code tip)
this version simply outputs a whole bunch of -1, but i thought id give you an update. Thanks!

Here's an example of what the others ment by pretending to execute the code. I assume that x starts out being set to 3 in my example. See what happens:

ChrisBrightwell
Apr 28, 2006, 03:18 AM
Here's the non-recursive algorithm I found in one of my old homework folders:


private static long fib(int x)
{
if(x == 0 || x == 1)
return x;

else
{
long back1 = 1;
long back2 = 0;
long result = 0;

for(int i=0; i<x-1; i++)
{
long sum = back1 + back2;
back2 = back1;
back1 = sum;
result = sum;
}

return result;
}
}

You can eliminate one of the variables in the else{}, but I didn't care that much back then, nor do I care to fool with it right now.

You get a rollover error at x==93. If you're using an int for x, you'll get a rollover error at x==47. There's some error checking to be done (check for non-negative integers, esp.), but you get the idea.

Also, for the record, the recursive algorithm becomes obnoxious at x==35 here on my Powerbook. :) I suspect my workstation at work (dual 3.5GHz Xeon w/ HT, 4GB RAM) wouldn't flinch until 40 or 45. I'll test it tomorrow.

We use a table lookup for this in the app I develop at work (as well as for our factorial "calculations"), since the set of answers is so small.

ChrisBrightwell
Apr 28, 2006, 02:36 PM
Also, for the record, the recursive algorithm becomes obnoxious at x==35 here on my Powerbook. :) I suspect my workstation at work (dual 3.5GHz Xeon w/ HT, 4GB RAM) wouldn't flinch until 40 or 45. I'll test it tomorrow.Haha OK ... It hit a similar "lag" at x==40. :)

To help n00bs reading this thread (and n00bs that will eventually read this thread), I did a bit of testing on the recursive vs non-recursive methods.

Here's the code I (tweaked and then) used to test:
import java.util.Date;

public class Fibonacci
{
public static void main(String[] args)
{

Date start_loop = new Date();

for(int x=0; x<50; x++)
{
Date start_fib = new Date();
long value = fib(x);
Date finish_fib = new Date();

long time_for_fib = finish_fib.getTime() - start_fib.getTime();

System.out.println("Input: " + x + ", Output: " + value + " (" + time_for_fib + " msec)");
}

Date finish_loop = new Date();

long total_elapsed = finish_loop.getTime() - start_loop.getTime();
System.out.println("total elapsed msec: " + total_elapsed);
}

private static long fib(int x)
{
if (x == 0 || x == 1)
return x;

else
return fib(x-1) + fib(x-2);
}
}


The machine here at work produced the following output:% version
Microsoft Windows XP [Version 5.1.2600]

% java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode)

% javac Fibonacci.java

% java -cp . Fibonacci
Input: 0, Output: 0 (0 msec)
Input: 1, Output: 1 (0 msec)
Input: 2, Output: 1 (0 msec)
Input: 3, Output: 2 (0 msec)
Input: 4, Output: 3 (0 msec)
Input: 5, Output: 5 (0 msec)
Input: 6, Output: 8 (0 msec)
Input: 7, Output: 13 (0 msec)
Input: 8, Output: 21 (0 msec)
Input: 9, Output: 34 (0 msec)
Input: 10, Output: 55 (0 msec)
Input: 11, Output: 89 (0 msec)
Input: 12, Output: 144 (0 msec)
Input: 13, Output: 233 (0 msec)
Input: 14, Output: 377 (0 msec)
Input: 15, Output: 610 (0 msec)
Input: 16, Output: 987 (0 msec)
Input: 17, Output: 1597 (0 msec)
Input: 18, Output: 2584 (0 msec)
Input: 19, Output: 4181 (0 msec)
Input: 20, Output: 6765 (0 msec)
Input: 21, Output: 10946 (0 msec)
Input: 22, Output: 17711 (0 msec)
Input: 23, Output: 28657 (0 msec)
Input: 24, Output: 46368 (0 msec)
Input: 25, Output: 75025 (0 msec)
Input: 26, Output: 121393 (15 msec)
Input: 27, Output: 196418 (0 msec)
Input: 28, Output: 317811 (0 msec)
Input: 29, Output: 514229 (16 msec)
Input: 30, Output: 832040 (0 msec)
Input: 31, Output: 1346269 (31 msec)
Input: 32, Output: 2178309 (32 msec)
Input: 33, Output: 3524578 (46 msec)
Input: 34, Output: 5702887 (79 msec)
Input: 35, Output: 9227465 (140 msec)
Input: 36, Output: 14930352 (219 msec)
Input: 37, Output: 24157817 (344 msec)
Input: 38, Output: 39088169 (578 msec)
Input: 39, Output: 63245986 (922 msec)
Input: 40, Output: 102334155 (1500 msec)
Input: 41, Output: 165580141 (2422 msec)
Input: 42, Output: 267914296 (3922 msec)
Input: 43, Output: 433494437 (6345 msec)
Input: 44, Output: 701408733 (10267 msec)
Input: 45, Output: 1134903170 (16673 msec)
Input: 46, Output: 1836311903 (27081 msec)
Input: 47, Output: 2971215073 (43722 msec)
Input: 48, Output: 4807526976 (70363 msec)
Input: 49, Output: 7778742049 (114147 msec)
total elapsed msec: 298880
... that's 114 seconds for fib(49)!

Swap out the recursive function for the non-recursive function, and your code will look like this:import java.util.Date;

public class Fibonacci
{
public static void main(String[] args)
{

Date start_loop = new Date();

for(int x=0; x<50; x++)
{
Date start_fib = new Date();
long value = fib(x);
Date finish_fib = new Date();

long time_for_fib = finish_fib.getTime() - start_fib.getTime();

System.out.println("Input: " + x + ", Output: " + value + " (" + time_for_fib + " msec)");
}

Date finish_loop = new Date();

long total_elapsed = finish_loop.getTime() - start_loop.getTime();
System.out.println("total elapsed msec: " + total_elapsed);
}

private static long fib(int x)
{
if(x == 0 || x == 1)
return x;

else
{
long back1 = 1;
long back2 = 0;
long result = 0;

for(int i=0; i<x-1; i++)
{
long sum = back1 + back2;
back2 = back1;
back1 = sum;
result = sum;
}

return result;
}
}
}

And my workstation here will kick out something like this:% version
Microsoft Windows XP [Version 5.1.2600]

% java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode)

% javac Fibonacci.java

% java -cp . Fibonacci
Input: 0, Output: 0 (0 msec)
Input: 1, Output: 1 (0 msec)
Input: 2, Output: 1 (0 msec)
Input: 3, Output: 2 (0 msec)
Input: 4, Output: 3 (0 msec)
Input: 5, Output: 5 (0 msec)
Input: 6, Output: 8 (0 msec)
Input: 7, Output: 13 (0 msec)
Input: 8, Output: 21 (0 msec)
Input: 9, Output: 34 (0 msec)
Input: 10, Output: 55 (0 msec)
Input: 11, Output: 89 (0 msec)
Input: 12, Output: 144 (0 msec)
Input: 13, Output: 233 (0 msec)
Input: 14, Output: 377 (0 msec)
Input: 15, Output: 610 (0 msec)
Input: 16, Output: 987 (0 msec)
Input: 17, Output: 1597 (0 msec)
Input: 18, Output: 2584 (0 msec)
Input: 19, Output: 4181 (0 msec)
Input: 20, Output: 6765 (0 msec)
Input: 21, Output: 10946 (0 msec)
Input: 22, Output: 17711 (0 msec)
Input: 23, Output: 28657 (0 msec)
Input: 24, Output: 46368 (0 msec)
Input: 25, Output: 75025 (0 msec)
Input: 26, Output: 121393 (0 msec)
Input: 27, Output: 196418 (0 msec)
Input: 28, Output: 317811 (0 msec)
Input: 29, Output: 514229 (0 msec)
Input: 30, Output: 832040 (0 msec)
Input: 31, Output: 1346269 (0 msec)
Input: 32, Output: 2178309 (0 msec)
Input: 33, Output: 3524578 (0 msec)
Input: 34, Output: 5702887 (0 msec)
Input: 35, Output: 9227465 (0 msec)
Input: 36, Output: 14930352 (0 msec)
Input: 37, Output: 24157817 (0 msec)
Input: 38, Output: 39088169 (0 msec)
Input: 39, Output: 63245986 (0 msec)
Input: 40, Output: 102334155 (0 msec)
Input: 41, Output: 165580141 (0 msec)
Input: 42, Output: 267914296 (0 msec)
Input: 43, Output: 433494437 (0 msec)
Input: 44, Output: 701408733 (0 msec)
Input: 45, Output: 1134903170 (0 msec)
Input: 46, Output: 1836311903 (0 msec)
Input: 47, Output: 2971215073 (0 msec)
Input: 48, Output: 4807526976 (0 msec)
Input: 49, Output: 7778742049 (0 msec)
total elapsed msec: 172


The "total time elapsed" values will be skewed a bit, since I'm doing time calcs in the loop, but you can fix that pretty easily. I'm partial to the elegance of the recursive solution, but I understand its pitfalls. Like I said, we use a table lookup here at work. :)

savar
Apr 28, 2006, 03:28 PM
hey all
well i was trying to write some code that would output the first 20 fibonacci numbers, but im having some trouble when i impliment it. whenever i try to run the program (java fibonacci 20) it gives me this error:

Did you get all of your problems sorted out, Phiber?

This thread got way off-topic :D

phiber optik
Apr 28, 2006, 07:55 PM
wow this turned into a long thread... :D
i just got back from school and i got a chance to read all this. I'm pretty sure ill get all my problems sorted out with all this code. if not, you'll definetly hear about it!
oh and to give a feeling of satisfaction to therevolution, i learned a ton flipping through my java book and looking stuff up online, as well as writing my buggy code. So youre method of teaching worked out for me! (and youre not a meanyhead, just a good teacher.)
thanks again for all the help and code.