
How would I go about doing this?
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 forloop 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?

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 ONEHALF 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 ...

Hey bro here's the logic for the problem
Code:
/**
* 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

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?

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 ...

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:
Code:
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're absolutely correct  this is the method of "log(base 2)" calculation using basic arithmetical operations.

Originally Posted by 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 ...
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
Code:
public static int getGuesses( int num )
{
return (int)Math.ceil( ( Math.log( Math.abs( num ) ) / Math.log( 2 ) ) );
}

Originally Posted by 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:
Code:
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

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.
Last edited by nspils; 10122005 at 06:55 PM.

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

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

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

Right  you would stop at 1  no where else to go  so if you get that far you have found it ...
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
