Results 1 to 17 of 17

Thread: Fibonacci Help

  1. #1
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default Fibonacci Help

    I have "homework" I have to print first 49 Fibonacci numbers

    means like this
    0
    1
    1
    2
    3
    5
    8
    13
    and so on...

    I do not want solution, I want to learn I want to feedback for approaching it
    this is what I got so far.
    PHP Code:
    public class Fib {
       public static void main (String args[]) {
    
            int x, y,count, sum,z;
            z = 0;
            count = 1;
            y =1;
            x =0;
    
            do {
    
            sum = x + y;
            sum += y;
    
            System.out.println(sum );
            count++;
    
    
            }while(count<=49);
       }
    }
    output is "2" 49 times.
    please give me some feedback should I put like for loop inside do loop.

    I also wan to print on parllel to these number the number line
    like

    1 2
    2 2
    3 2
    4 2
    5 2
    6 2
    7 2
    8 2
    9 2
    10 2
    .
    .
    .
    49 2

    2 because is my output so far,
    I tried

    PHP Code:
    public class Fib {
       public static void main (String args[]) {
    
            int x, y,count, sum,z;
            z = 0;
            count = 1;
            y =1;
            x =0;
    
            do {
    
            sum = x + y;
            sum += y;
    
            for(int i=1;i<=49;i++)
            System.out.println(i + " " + sum);
            count++;
    
    
            }while(count<=49);
       }
    }
    this one is printing weird

    help me fix this too



    Thank you
    Last edited by zit1343; 01-23-2011 at 06:13 PM.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

    You need to change x and y in the loop for the sum to change. Figure out the logic of how you'd solve this on paper first, and then you'll more easily translate it to Java. Please post your next attempt if it fails.

    Much luck!!

  3. #3
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    Hey I think I am making progress, but not much, it is print 49 squence but printing the powers of 2 till 49.
    may be my formula is wrong.



    PHP Code:
    public class sum {
            public static void main (String args[]) {
    
            long sum, x = 0, y = 1;
    
                    for(int i=0;i<=49;i++) { // instead of using do while 49, this i will be printed 49 times so it will be same thing... 
                                                    //so I won't be printed 49 times but y will be printed 49 times 
    
                            sum = x;
                            x=y;
                            y =sum +y;
    
                    System.out.println(y);
    
                    }
            }
    }
    Last edited by zit1343; 01-23-2011 at 08:29 PM.

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    Java Code:
    sum = x;
    x=y;
    y =sum +y;

    This doesn't look right.

    Consider the following showing the Fibonacci sequence being built up one step at a time.

    Java Code:
    x  y sum
    0  1  1  
    
       x  y sum
    0  1  1  2
    
          x  [color=blue]y[/color] [color=red]sum[/color]
    0  1  1  [color=blue]2[/color]  [color=red]3[/color]
    
             [color=blue]x[/color]  [color=red]y[/color] [color=green]sum[/color]
    0  1  1  [color=blue]2[/color]  [color=red]3[/color]  [color=green]5[/color]
    How would we get from the second to last step (x is 1, y is 2, sum is 3) to the last one?

    Java Code:
    [color=blue]x[/color] = [color=blue]???[/color];
    [color=red]y[/color] = [color=red]???[/color];
    [color=green]sum[/color] = [color=green]???[/color];

  5. #5
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    thanx man tht worked but can you explain me first loop.

    sum = x;
    x=y;
    y =sum +y;

    for first loop
    sum = 0;
    x=1;
    y = 0 + 1;
    so for i = 0, y = 1

    2nd loop
    sum = 0;
    x=1;
    y = 0 + 1;
    i = 2, y = 1 again, I m not understanding formula corretly.

    Java Code:
    x  y sum
    0  1  1
    how is sum = 1 if, forumla says sum = x;
    so x so 0;
    sum = 0(x)
    x = 1(y)
    y = 0(sum) + 1(y)

    for i = 0, y = 1

    i dont get it

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    how is sum = 1 if, forumla says sum = x;

    I didn't have that formula in mind. The most natural meaning for "sum" (for me, at least) would be sum=x+y.

    You can use the variables with any meaning you like - just so long as the produce the right sequence! If you wonder why you get the output you do, replace

    Java Code:
    System.out.println(y);

    with the more informational

    Java Code:
    System.out.println("At the end of loop " + i);
    System.out.println("    sum=" + sum);
    System.out.println("      x=" + x);
    System.out.println("      y=" + y);

    This will tell you exactly how the variables' values change from one time around the loop to the next.

  7. #7
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    that helps to see what is end of each loop
    my defination of sum is also sum = x + y; but didn't declare it any where


    PHP Code:
    
    
    At the end of loop 0
        sum=0
          x=1
          y=1
    
    At the end of loop 1
        sum=1 // is this sum coming from y from end of loop 0?
          x=1
          y=2
    // what i m not understanding is how can I have sum before even telling that sum is x + y.
    At the end of loop 2
        sum=1 // where did this one come from?
          x=2
          y=3
    // and above in loop 2 y is doing job of holding sum of 2, like sum =1 and x =2  so 2 + 1 = to y = 3 
    At the end of loop 3
        sum=2
          x=3
          y=5
    // same here (sum=2) + (x =3)  =to 5
    At the end of loop 4
        sum=3
          x=5
          y=8
    At the end of loop 5
        sum=5
          x=8
          y=13
    Last edited by zit1343; 01-23-2011 at 09:58 PM.

  8. #8
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    my defination of sum is also sum = x + y; but didn't declare it any where

    I don't really understand this. sum is whatever you make it - and what your code says is "sum=x".

    That is why I suggested you replace the first three lines of the for loop. My post #4 tried to use colours to show how the values of x, y and sum can be calculated in terms of their values at the end of the previous loop.

    x in the last line is actually equal to y at the end of the previous loop. Similarly for y in the last line - it is equal to something at the end of the previous loop.

    Again, you could try to use the following in your for loop:

    Java Code:
    [color=blue]x[/color] = [color=blue]y[/color];  // ie the new value of x is the old value of y
    [color=red]y[/color] = [color=red]???[/color];
    [color=green]sum[/color] = [color=green]???[/color];

  9. #9
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    I did replace and I do get output
    ok let me try to explain it again
    Java Code:
    x  y sum
    0  1  1   // if sum of 0 & y = 1 
    
       x  y sum
    0  1  1  2
    
          x  y sum
    0  1  1  2  3
    
             x  y sum
    0  1  1  2  3  5
    PHP Code:
    sum = x; why do we have sum = x which = to 0 in first loop
    x=y; // x = to y which is 1
    y =sum +y; // so y = to 0 + 1 == to 1
    
    why the order like this sum goes first
    I don't not understand why the code is in this order

    sum = x;
    x=y;
    y =sum +y;
    Last edited by zit1343; 01-23-2011 at 11:29 PM.

  10. #10
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Think about it logically
    Java Code:
    sum = x;
    x=y;
    y =sum +y;
    the first line stores the value of x, why? because the second line changes x, so if you didn't store the original value of x first you would lose x.

    the third line is basically adding the previous two numbers.

    the fibb starts at 0, 1

    so sum = 0, x = 1, y = 1

    next time through

    sum = 1, x = 1, y = 2

    next

    sum = 1, x = 2, y = 3.

    if you used an array think of sum as current index - 2, and x as current index - 1

  11. #11
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    see I was thinking at beginning x was = to 0;
    so it stored 0 and y = 1
    long x = 0, y = 1, sum;

    sum= 0; // sum = x;
    x=1; // x = y;
    y= 0 + 1 // y = sum + y;

    so for next loop

    see I was thinking at beginning x was = to 0;
    so it stored 0 and y = 1
    long x = 0, y = 1, sum;

    sum= 0; // sum = x;
    x=1; // from previous loop x = y;
    y= 0 + 1 // & sum still equal to zero // y = sum + y;

    do you see where i am lost?
    what I am thinking is why is it store it first in sum why not after
    like
    x=0
    y=1
    sum=1+0; = 1;

    thank you

  12. #12
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    On the second loop everything changes

    sum gets set to whatever x was after the first loop, so if x did start at 0, and y was 1, after the first loop, x would be set to y, (1)

    So on the second loop, sum = x or 1
    x = y or 1
    y = sum + x or 1 + 1.

    on the next time through everything changes again, sum will be 1, x will be 2, and y will be 2 + 1

    You could change the sum variable it may seem a little confusing since it's really being used to store what x is before x is changed, the name might be causing some confusion.

  13. #13
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    oh oky tht make more sense, but what about the order

    so on third loop
    1: sum = x <-- will change 2nd but it will get value from the line below
    2: x = <--- this will change first y will be the value of y from last loop
    3: y = sum + y <-- and this one is will add it

  14. #14
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    your first step is incorrect, it doesn't really get the number from the line below, the variable x is declared earlier in the program, it is taking the information from there, after the first loop it changes all the values and then you change them again inside the loop, the order comes down to saving one variable, then changing the variable you just saved and adding them together.

    Java Code:
    int x = 1;
    int y;
    int lim
    Scanner scan = new Scanner(System.in);
    
    
    for(int i = 0; i < lim; i++){
      int tmp = x;//set tmp to store the value of x before making a change to it
      x = y;//change the value of x, since you are moving up into the sequence it should continually change
      y = tmp + x;//finds the next number in the series
    
      System.out.println(y); //print the current number in the fibb series.
    }
    You dont have to declare tmp outside the loop also, it will still work as expected, the variable tmp is never really used for more then just temporarily storing x.

    Also, did you figure out the prime problem?

  15. #15
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    thanx alot man tht make more sense, my variable sum was messing me up.

    so tmp will just store the current value of x into temp, and after tht value of x will change and will take a value of last y, and 3rd step y will add temp & y
    hope fully I understood it right..
    thanx again..

    I did get the prime one working but still need to give time and understand the math.sqrt part which make it more efficient..

    this is my homework which is due tomm so I had to stop on prime part and finish this..
    I have little problem in this program is tht

    output should look like this
    Java Code:
    0 0
    1 1
    2 1
    3 2
    4 3
    5 5
    ..
    ..
    ..
    46 1836311903
    47 2971215073
    48 4807526976
    and mine looks like

    Java Code:
    0 1
    1 2
    2 3
    3 5
    4 8
    ...
    ...
    ...
    
    46 4807526976
    47 7778742049
    48 12586269025
    PHP Code:
    public class sum {
            public static void main (String args[]) {
    
            long x = 0, y = 1,temp;
    
                    for(int i=0;i<=48;i++) {
                    temp = x;
                    x=y;
                    y =temp +y;
    
            System.out.println(i + " " +  y);
    
                    }
            }
    }

  16. #16
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Im not sure if it's the most elegant solution, but it's how I would do it.

    in the loop add something like:
    Java Code:
    if(i == 0 || i == 1){
      System.out.println(i + " " + i);
    }
    I just wrote the code and I got the output:
    Java Code:
    0 0
    1 1
    2 1
    3 2
    4 3
    5 5
    6 8
    7 13
    8 21
    9 34
    10 55
    ...
    46 1836311903
    47 2971215073
    48 4807526976
    49 7778742049
    check the prime thread I am going to explain the reason for sqrt being used.
    Last edited by sunde887; 01-24-2011 at 01:57 AM. Reason: fixed output

  17. #17
    zit1343 is offline Member
    Join Date
    Jan 2011
    Posts
    17
    Rep Power
    0

    Default

    great man, I working on this for lil bit and thanx again so much, I still need to read up on the post you made.

Similar Threads

  1. Fibonacci sequece
    By Bgreen7887 in forum New To Java
    Replies: 10
    Last Post: 12-03-2010, 08:27 PM
  2. Fibonacci sequence
    By ŖΫ ỏ Ңόρę in forum New To Java
    Replies: 6
    Last Post: 03-25-2010, 07:59 AM
  3. help with fibonacci
    By likemine in forum New To Java
    Replies: 8
    Last Post: 01-07-2010, 03:32 AM
  4. help with fibonacci problem
    By thekrazykid in forum New To Java
    Replies: 4
    Last Post: 12-12-2008, 11:41 PM
  5. Fibonacci Algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 05:25 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •