1. Member Join Date
Feb 2013
Posts
1
Rep Power
0

## 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  Reply With Quote

2. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## 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".)  Reply With Quote

3. ## Re: need help

Moved from Forum Lobby. teyyare, please go through the Forum Rules, especially the third paragraph. Also go through http://www.java-forums.org/forum-gui...w-members.html and BB Code List - Java Programming Forum - Learn Java Programming and edit your post accordingly.

db  Reply With Quote

#### Posting Permissions

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