# need help

• 02-04-2013, 11:24 PM
teyyare
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
• 02-05-2013, 12:07 AM
pbrockway2
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".)
• 02-06-2013, 08:04 AM
DarrylBurke
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