1. ## 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. 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. I'm thinking its log base 2 of 1000... 9.something so yes 10.

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

5. 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. 10 for binary search. Forgotten all my search algorithms already... Hehehe.. Only remember binary & bubble.

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

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

#### Posting Permissions

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