java programming help (again)

Discussion in 'Mac Programming' started by phiber optik, Apr 26, 2006.

  1. macrumors newbie

    Joined:
    Apr 25, 2006
    #1
    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;
    }
    }
     
  2. jsw
    Moderator emeritus

    jsw

    Joined:
    Mar 16, 2004
    Location:
    Andover, MA
    #2
    Try changing the method signature to:

    Code:
    public [b]static[/b] void main(String[] args)
     
  3. thread starter macrumors newbie

    Joined:
    Apr 25, 2006
    #3
    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?
     
  4. macrumors 6502

    Joined:
    May 12, 2003
    #4
    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'.
     
  5. thread starter macrumors newbie

    Joined:
    Apr 25, 2006
    #5
    yeah that could affect it :p
    but im still getting the same output
    hmmm.....
     
  6. macrumors 6502

    Joined:
    May 12, 2003
    #6
    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! :)
     
  7. Administrator

    Doctor Q

    Staff Member

    Joined:
    Sep 19, 2002
    Location:
    Kepler-452b
    #7
    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.
     
  8. thread starter macrumors newbie

    Joined:
    Apr 25, 2006
    #8
    if a = 2
    while (something)
    b = (a -2) + (a -1)
    how do i have the program ignore a = 2 the second time around?
     
  9. Administrator

    Doctor Q

    Staff Member

    Joined:
    Sep 19, 2002
    Location:
    Kepler-452b
    #9
    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 [code] and [/code] tags around it in your forum posts, it'll stay formatted correctly, e.g.,
    Code:
    public static void main (String args[]) {
            int input = Integer.parseInt(args[0]);
            int result = fibonacci(input);
            System.out.println(result);
    }
     
  10. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #10
    Your logic is flawed.

    Code:
      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.

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

    Joined:
    Apr 25, 2006
    #11
    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!!
     
  12. thread starter macrumors newbie

    Joined:
    Apr 25, 2006
    #12
    and here's the code i have so far: (thanks for the /code tip)
    Code:
     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!
     
  13. macrumors 603

    janey

    Joined:
    Dec 20, 2002
    Location:
    sunny los angeles
    #13
    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
    Code:
    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.
     
  14. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #14
    ... Did you look at the code I posted?

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

    janey

    Joined:
    Dec 20, 2002
    Location:
    sunny los angeles
    #15
    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
    Code:
    int Factorial ( int number )    {
        if ( number == 1 )  {
            return number;
        }
        else    {
            return number * Factorial( number - 1 );
        }
    }
    
    factorial using iteration
    Code:
    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..)
     
  16. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #16
    No, I'm well aware of the problem with higher values in this situation ... but he only has to count the first 20 values.
     
  17. Administrator

    Doctor Q

    Staff Member

    Joined:
    Sep 19, 2002
    Location:
    Kepler-452b
    #17
    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.
     
  18. macrumors 603

    janey

    Joined:
    Dec 20, 2002
    Location:
    sunny los angeles
    #18
    Well then, why not a
    Code:
    System.out.println("0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181");
    
    :eek: :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..)
     
  19. Administrator

    Doctor Q

    Staff Member

    Joined:
    Sep 19, 2002
    Location:
    Kepler-452b
    #19
    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:
    Code:
    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.
     
  20. macrumors 603

    janey

    Joined:
    Dec 20, 2002
    Location:
    sunny los angeles
    #20
  21. macrumors 603

    gekko513

    Joined:
    Oct 16, 2003
    #21
    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:
     

    Attached Files:

  22. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #22
    Here's the non-recursive algorithm I found in one of my old homework folders:

    Code:
      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.
     
  23. macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #23
    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:
    PHP:
    import java.util.Date;

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

        
    Date start_loop = new Date();

        for(
    int x=0x<50x++)
        {
          
    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: " ", 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 (
    == || == 1)
          return 
    x

        else 
          return 
    fib(x-1) + fib(x-2);
      }
    }
    The machine here at work produced the following output:
    PHP:
    version
    Microsoft Windows XP 
    [Version 5.1.2600]

    java -version
    java version 
    "1.5.0_06"
    Java(TM2 Runtime EnvironmentStandard Edition (build 1.5.0_06-b05)
    Java HotSpot(TMClient VM (build 1.5.0_06-b05mixed mode)

    javac Fibonacci.java

    java -cp Fibonacci
    Input
    0Output(0 msec)
    Input1Output(0 msec)
    Input2Output(0 msec)
    Input3Output(0 msec)
    Input4Output(0 msec)
    Input5Output(0 msec)
    Input6Output(0 msec)
    Input7Output13 (0 msec)
    Input8Output21 (0 msec)
    Input9Output34 (0 msec)
    Input10Output55 (0 msec)
    Input11Output89 (0 msec)
    Input12Output144 (0 msec)
    Input13Output233 (0 msec)
    Input14Output377 (0 msec)
    Input15Output610 (0 msec)
    Input16Output987 (0 msec)
    Input17Output1597 (0 msec)
    Input18Output2584 (0 msec)
    Input19Output4181 (0 msec)
    Input20Output6765 (0 msec)
    Input21Output10946 (0 msec)
    Input22Output17711 (0 msec)
    Input23Output28657 (0 msec)
    Input24Output46368 (0 msec)
    Input25Output75025 (0 msec)
    Input26Output121393 (15 msec)
    Input27Output196418 (0 msec)
    Input28Output317811 (0 msec)
    Input29Output514229 (16 msec)
    Input30Output832040 (0 msec)
    Input31Output1346269 (31 msec)
    Input32Output2178309 (32 msec)
    Input33Output3524578 (46 msec)
    Input34Output5702887 (79 msec)
    Input35Output9227465 (140 msec)
    Input36Output14930352 (219 msec)
    Input37Output24157817 (344 msec)
    Input38Output39088169 (578 msec)
    Input39Output63245986 (922 msec)
    Input40Output102334155 (1500 msec)
    Input41Output165580141 (2422 msec)
    Input42Output267914296 (3922 msec)
    Input43Output433494437 (6345 msec)
    Input44Output701408733 (10267 msec)
    Input45Output1134903170 (16673 msec)
    Input46Output1836311903 (27081 msec)
    Input47Output2971215073 (43722 msec)
    Input48Output4807526976 (70363 msec)
    Input49Output7778742049 (114147 msec)
    total elapsed msec298880
    ... that's 114 seconds for fib(49)!

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

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

        
    Date start_loop = new Date();

        for(
    int x=0x<50x++)
        {
          
    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: " ", 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(
    == || == 1)
          return 
    x;

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

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

          return 
    result
        }
      }
    }
    And my workstation here will kick out something like this:
    PHP:
    version
    Microsoft Windows XP 
    [Version 5.1.2600]

    java -version
    java version 
    "1.5.0_06"
    Java(TM2 Runtime EnvironmentStandard Edition (build 1.5.0_06-b05)
    Java HotSpot(TMClient VM (build 1.5.0_06-b05mixed mode)

    javac Fibonacci.java

    java -cp Fibonacci
    Input
    0Output(0 msec)
    Input1Output(0 msec)
    Input2Output(0 msec)
    Input3Output(0 msec)
    Input4Output(0 msec)
    Input5Output(0 msec)
    Input6Output(0 msec)
    Input7Output13 (0 msec)
    Input8Output21 (0 msec)
    Input9Output34 (0 msec)
    Input10Output55 (0 msec)
    Input11Output89 (0 msec)
    Input12Output144 (0 msec)
    Input13Output233 (0 msec)
    Input14Output377 (0 msec)
    Input15Output610 (0 msec)
    Input16Output987 (0 msec)
    Input17Output1597 (0 msec)
    Input18Output2584 (0 msec)
    Input19Output4181 (0 msec)
    Input20Output6765 (0 msec)
    Input21Output10946 (0 msec)
    Input22Output17711 (0 msec)
    Input23Output28657 (0 msec)
    Input24Output46368 (0 msec)
    Input25Output75025 (0 msec)
    Input26Output121393 (0 msec)
    Input27Output196418 (0 msec)
    Input28Output317811 (0 msec)
    Input29Output514229 (0 msec)
    Input30Output832040 (0 msec)
    Input31Output1346269 (0 msec)
    Input32Output2178309 (0 msec)
    Input33Output3524578 (0 msec)
    Input34Output5702887 (0 msec)
    Input35Output9227465 (0 msec)
    Input36Output14930352 (0 msec)
    Input37Output24157817 (0 msec)
    Input38Output39088169 (0 msec)
    Input39Output63245986 (0 msec)
    Input40Output102334155 (0 msec)
    Input41Output165580141 (0 msec)
    Input42Output267914296 (0 msec)
    Input43Output433494437 (0 msec)
    Input44Output701408733 (0 msec)
    Input45Output1134903170 (0 msec)
    Input46Output1836311903 (0 msec)
    Input47Output2971215073 (0 msec)
    Input48Output4807526976 (0 msec)
    Input49Output7778742049 (0 msec)
    total elapsed msec172

    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. :)
     
  24. macrumors 68000

    savar

    Joined:
    Jun 6, 2003
    Location:
    District of Columbia
    #24
    Did you get all of your problems sorted out, Phiber?

    This thread got way off-topic :D
     
  25. thread starter macrumors newbie

    Joined:
    Apr 25, 2006
    #25
    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.
     

Share This Page