Results 1 to 9 of 9

Thread: Algorithm problem

  1. #1

    Default Algorithm problem

    Suppose i was thinking of a number between 1 and 1000 inclusive and for every attempt to guess my secret number i;ll tell you whether your guess is higher or lower than my secret number.. In the worst case how many guesses do u need to figure out what is my secret number?

    I don't know the answer, but im guessing its 10, using the binary search algorithm?

    Anybody?

  2. #2

    Default

    worst case is 999 lor.
    Your secret number is 1000, and i start choosing from 1.


    Fastest way is to do a quick sort i guess. Take a pivot and halve it.

  3. #3

    Default

    I'm thinking its log base 2 of 1000... 9.something so yes 10.

  4. #4

    Default

    why not i start 1st? my secret number 1-1000.
    Objection !!!

  5. #5
    Senior Member jOhO's Avatar
    Join Date
    Apr 2003
    Location
    Singapore
    Posts
    6,485

    Default

    Quote Originally Posted by junyang
    Suppose i was thinking of a number between 1 and 1000 inclusive and for every attempt to guess my secret number i;ll tell you whether your guess is higher or lower than my secret number.. In the worst case how many guesses do u need to figure out what is my secret number?

    I don't know the answer, but im guessing its 10, using the binary search algorithm?

    Anybody?
    i think using that rule gives u the BEST case scenario...

  6. #6
    Member
    Join Date
    Feb 2004
    Location
    Bedok
    Posts
    716

    Default

    10 for binary search. Forgotten all my search algorithms already... Hehehe.. Only remember binary & bubble.

  7. #7
    Member
    Join Date
    Oct 2002
    Location
    Hougang
    Posts
    319

    Default

    Quote Originally Posted by laugh
    worst case is 999 lor.
    Your secret number is 1000, and i start choosing from 1.


    Fastest way is to do a quick sort i guess. Take a pivot and halve it.
    Believe what Laugh said is correct. That is the assumption the guesser isnt that "intelligent" enough and starts from 1, 2, 3, ...

    unless if he starts his guess from 500 and keep halving his guess.. den maybe could be 10...

  8. #8
    Senior Member
    Join Date
    Jan 2002
    Location
    Northwest
    Posts
    5,011

    Default

    The person guessing the number can employ different tactics/algorithms.

    For each tactic/algorithm, the best case is usually 1, i.e., correct guess on the 1st attempt.

    The worst cast is a measure of how "good" each tactic/algorithm is.

    For example, if the person simply ignoe the feedback about wheter his previous guess is bigger or smaller then the actual number, but simply start his guesses from 1, 2, 3...etc, then the worst case is 100 guesses before he can hit the number.

    If the tactic/algorithm is simply to choose a random number for each guess with no repetition, but still ignoring the feedback on bigger or smaller, then the worst case is also 1000.

    If the tactic/algorithm is to keep track of previous guesses, as well as take in feed back on bigger or smaller, and choose a random number within the appropriate range of numbers each time, then the worst case is still 1000 but the probability of the worst case happenning is much much smaller than the worst case of the previous 2 tactics.

    If the tactic is to use a binary serach method then the worst case is 10.

    Sot he best of the worst cases is the binary search method.
    As complexity rises, precise statements lose meaning and meaningful statements lose precision.

  9. #9
    Member
    Join Date
    Jun 2004
    Location
    Leith Road
    Posts
    134

    Default

    Quote Originally Posted by jOhO
    i think using that rule gives u the BEST case scenario...
    Actually, the best case scenario is 1.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •