paulwhelan
asked on
logic question
i have no idea where i should ask this question but here is as good as anywhere i guess...
If someone writes down a random number (natural number) what s the best strategy for searching a tree of the following type in order to guess the number:
empty
/ | | \ .....etc
0 1 3 4 .....etc
/ | \ /\ /\ /\ ....etc
00 01 02.........etc
if that makes any sense?
basically its to do with depthfirst/breadthfirst strategies
and id like to know the best strategy for this search without going into an infinite loop...
thanks
paul
If someone writes down a random number (natural number) what s the best strategy for searching a tree of the following type in order to guess the number:
empty
/ | | \ .....etc
0 1 3 4 .....etc
/ | \ /\ /\ /\ ....etc
00 01 02.........etc
if that makes any sense?
basically its to do with depthfirst/breadthfirst strategies
and id like to know the best strategy for this search without going into an infinite loop...
thanks
paul
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
binary search, like the number guessing game. For a number n between L and N, make the first guess at (L+N)/2. if x is smaller, the range becomes L .. N/2 (guess at (L+N)/4). If x is larger, the search range becomes (L+N)/2 +1 .. N (guess at ((L+N)/2 + 1 + N)/2). etc...
qn: y is 00 different from 0? then it's not just a no?
anyway, since there are infinite natural numbers, BFS is the way to go...
easy implementation (if 00 and 000 are different from 0 say) is
go thru all single digit nos, ie. [0, 9]
then double [00, 99]
then triple blahblah
if 00 is same as 0 then just go from 0 onwards...
of course that is if u can only get the answer to "is __ the number?"
otherwise binary would be best if u can get the answer to "is __ bigger/less than the number?"
anyway, since there are infinite natural numbers, BFS is the way to go...
easy implementation (if 00 and 000 are different from 0 say) is
go thru all single digit nos, ie. [0, 9]
then double [00, 99]
then triple blahblah
if 00 is same as 0 then just go from 0 onwards...
of course that is if u can only get the answer to "is __ the number?"
otherwise binary would be best if u can get the answer to "is __ bigger/less than the number?"
I think ur question is similar to
searching words in Dictionary.
I would also like to know the answer.
searching words in Dictionary.
I would also like to know the answer.
Are you guessing digit-by-digit or the while number (i.e., 123 as "0?", "No.", "1?", "Yes; first digit correct."; "0?", "No.", etc.), or "0?", "No 0.", "1?", "Yes, there's (one or more) 1."?
How do you decide on your branches?
What information do you recieve when you guess?
What information do you recieve when you guess?
Pls give more info what you want to do exactly!.