How would I go about doing this?

[Dark Rain]

Problem Statement: How many guesses does it take to guess a secret number between 1 and N? For example, take a number between 1 and 100, I'll tell you whether you guess to high or too low. An intellegent first guess would be 50. If that's too low an intellegent second guess would be 75, and so on. If we continue to divide the range in half, we'll eventually get down to one number. Because you can divide 100 seven times (50, 25, 12, 6, 3, 1, 0), it will take at most seven guesses to guess a number between 1 and 100. Write a Java applet that lets the user input a positive integer, N, and then reports how many guesses it would take to guess anumber between 1 and N.

I suppose a for-loop would be needed, but I'm not sure what exactly it's asking me to do. Anyone have any takes on what I'm supposed to do?

[nspils]

Is this a logic question or a programming question? The call of the question does not appear to be asking you to write a program which looks for a particular guess ... it is asking you for the maximum number of guesses it will take you to find the number in question, IF EACH GUESS IS EXACTLY ONE-HALF OF A GIVEN RANGE ...

So ... can you think of a calculation which would allow you to reach this answer? dividing by two should give you a hint ...

[mohit]

Hey bro here's the logic for the problem

/**
 * mohit
 * aggarwal dot mohit at gmail dot com
 */
public class Logic
{
	public static void main( String s[] )
	{
		System.out.println( getGuesses( 100 ) );
		System.out.println( getGuesses( 200 ) );
		System.out.println( getGuesses( 1000 ) );
	}
	
	public static int getGuesses( int num )
	{
		return ( 1 + (int)( Math.log( Math.abs( num ) ) / Math.log( 2 ) ) );
	}
}

Sample output:
7
8
10

[Dark Rain]

That's interesting mohit. Although I'm new to Java, so is Math.log is taking a logarithm correct? And what is Math.abs? Absolute value?

[nspils]

Wouldn't it be more correct to have the answer be the ceiling of the log (base 2) of N? Math.ceil( (double)Math.log ( N ) / Math.log(2)) ? By mohit's formula, the maximum number of guesses for N=16 would be five, but the correct number is 4 ...

[Dark Rain]

I haven't actually taken Calculus yet, so I'm not really sure what that does =p. Although if someone could explain I would be interested.

I just used a while loop:

	while (n >= 1)
			{
				n /= 2;
				count++;
				userNumber = count;
			}

It did the same thing as the formula does. Is there a benefit to doing it the Calculus way (other than saving seven lines of code)?

[nspils]

You're absolutely correct - this is the method of "log(base 2)" calculation using basic arithmetical operations.

[mohit]

Wouldn't it be more correct to have the answer be the ceiling of the log (base 2) of N? Math.ceil( (double)Math.log ( N ) / Math.log(2)) ? By mohit's formula, the maximum number of guesses for N=16 would be five, but the correct number is 4 ...

You are right. I have added 1 after casting the result to integer under the assumption that it will always be a decimal number. My mistake. Correct code should be

	public static int getGuesses( int num )
	{
		return (int)Math.ceil( ( Math.log( Math.abs( num ) ) / Math.log( 2 ) ) );
	}

[mohit]

I haven't actually taken Calculus yet, so I'm not really sure what that does =p. Although if someone could explain I would be interested.

I just used a while loop:

	while (n >= 1)
			{
				n /= 2;
				count++;
				userNumber = count;
			}

It did the same thing as the formula does. Is there a benefit to doing it the Calculus way (other than saving seven lines of code)?

You can approach the problem this way also. And thats how I did it when I first made number guessing game in first year . What my code really do is that

1) It finds out what is the value of x in 2^x = (passed number)
2) If this value has some non zero decimal part than return the integer higher than current.

I am divideing by Math.log( 2 ) because by default log is taken on base e=2.73. So in case I wanted to find the value of x in case 3 ^ x = (passed number). I would have devided by Math.log( 3 ).

Regards,
Mohit

[nspils]

log (base b) (x) = log (base a) (x) / log (base a) (b), no matter what bases you are using.

Java's Math class logarithm methods use either natural log [ln or log( base n)] or log (base 10). In order to do a caculation regarding base 2 (done frequently in computing) we need to convert to base 2 using that formula.

[Dark Rain]

Also, when using the while loop method and inputting 16, it returns 5. How would I go about fixing this?

[nspils]

change the condition of the loop to be while (n > 1)

[Dark Rain]

So for 16 it would be: 8, 4, 2, 1 instead of 8, 4, 2, 1, 0 right?

[nspils]

Right - you would stop at 1 - no where else to go - so if you get that far you have found it ...