How would I go about doing this?

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Sep 2005
Posts
74

## 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 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?

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 ...

3. Registered User
Join Date
Oct 2005
Posts
40
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

4. Registered User
Join Date
Sep 2005
Posts
74
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?

5. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 ...

6. Registered User
Join Date
Sep 2005
Posts
74
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)?

7. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
You're absolutely correct - this is the method of "log(base 2)" calculation using basic arithmetical operations.

8. Registered User
Join Date
Oct 2005
Posts
40
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 ) ) );
}```

9. Registered User
Join Date
Oct 2005
Posts
40
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

10. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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; 10-12-2005 at 05:55 PM.

11. Registered User
Join Date
Sep 2005
Posts
74
Also, when using the while loop method and inputting 16, it returns 5. How would I go about fixing this?

12. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
change the condition of the loop to be while (n > 1)

13. Registered User
Join Date
Sep 2005
Posts
74
So for 16 it would be: 8, 4, 2, 1 instead of 8, 4, 2, 1, 0 right?

14. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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
•

 FAQ Latest Articles Java .NET XML Database Enterprise