How would I go about doing this?


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 14 of 14

Thread: How would I go about doing this?

  1. #1
    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. #2
    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. #3
    Join Date
    Oct 2005
    Posts
    40

    Arrow

    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. #4
    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. #5
    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. #6
    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. #7
    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. #8
    Join Date
    Oct 2005
    Posts
    40

    Thumbs up

    Quote 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. #9
    Join Date
    Oct 2005
    Posts
    40
    Quote 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. #10
    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. #11
    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. #12
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    change the condition of the loop to be while (n > 1)

  13. #13
    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. #14
    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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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