Results 1 to 3 of 3

Thread: need help

  1. #1
    teyyare is offline Member
    Join Date
    Feb 2013
    Posts
    1
    Rep Power
    0

    Default need help

    Could anyone help the following please;

    This program computes the value of the recursive function F(n) for each integer n ranging from 1 to 1024.

    package fibonacci;

    public class FibbonaciHW {

    static int count = 0;

    public static void main (String [] args)
    {
    int lim = 1024;
    for (int n = 1; n <= lim; n++)
    {
    count = 0;
    int m = F(n);
    System.out.print("F(" + n + ") = " + m);
    System.out.println(" count = " + count);
    }
    }

    public static int F(int n)
    {
    count++;
    if (n == 0) return 1;
    if (n%10 == 0) return (F(n/2) + F(n/5));
    else
    if (n%6 == 0) return(F(n/2) + F(n/3));
    else return(F(n/3) + F(n/5));
    }
    }


    where k/m denotes the integer division (for example, 11/2 = 5, 10/2 = 5, 10/3 = 3, 9/3 = 3, etc.), and k%m is the remainder of integer division k/m (for example, 11%2 = 1, 10%2 = 0, 11%3 = 2, 10%3 = 1, etc.),

    and counts its own worst-case running time measured by the number of calls to function F.

    I would like to convert this program onto a complete and running program that for every size of integer n ranging from 1 to 10 computes and outputs the worst-case running time T(n) (measured by the number of calls to function F) of F.

    Requirements:

    1. The size of input n is the number of bits needed for representation of the value of n, excluding any leading zeros. (Hint: the size of n =

    (int)Math.floor(Math.log(n)/Math.log(2))+1

    2. The actual running time of the program is measured by counter count that counts the number of times that the function F is called.

    3. The program must print its own worst-case running time T(size) as a function of the size of input (NOT of the input n itself) together with the actual numeric value of T(size). (If different inputs n of the same size result in different number of calls to method F then the maximum of the number of said calls yields the value of T(size).)

    4. The only methods that is allowed to use are in java.lang.Math.
    5. An example of one line (out of several) of output should be:

    Worst-case running time T(4) = 15

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

    Default Re: need help

    So what is the problem? Ie what are you stuck with?

    The first couple of steps seem to be (1) Understanding the definition of F. You should be able to evaluate F(n) for modest values of n, eg see that F(7)=4 and be able to predict the corresponding value of count. And (2) understanding the definition of T(size), again for modest values of size. What values of n have a size of 3? What are the count values associated with evaluating F(n) for each of these values? Hence what is T(3)?

    Avoid rushing into code until you are clear about the algorithm you are attempting to code. (Sorry for all the questions, but being able to answer them is what I mean by "understand".)

  3. #3
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,189
    Rep Power
    19

    Default Re: need help

    Moved from Forum Lobby. teyyare, please go through the Forum Rules, especially the third paragraph. Also go through Guide For New Members and BB Code List - Java Programming Forum - Learn Java Programming and edit your post accordingly.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

Posting Permissions

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