• C

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
paulwhelanAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

curriCommented:
Some questions:

Are those numbers or strings ? (00, 01, ...)

Are the numbers in some order in the tree ?

Is the tree finite ?

BTW, is it a tree or a graph ?

In general, you can search any finite tree/graph with either depth-first or breadth-first strategy, without any problem. Breadth-first consumes much more memory, and is usually harder to implement (so depth-first would be the method of choice, unless we know something else :).

For an infinite tree/graph depth first is NOT guaranteed to find the answer, I think, while breadth-first is.

Also, if you have more info about the tree and/or nodes, some other algorithms may be better (A*, branch & bound etc), and if the nodes are ordered, then of course you can do much better :)

Orlando
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
KangaRooCommented:
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...
0
_lychee_Commented:
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?"
0
Making Bulk Changes to Active Directory

Watch this video to see how easy it is to make mass changes to Active Directory from an external text file without using complicated scripts.

basantCommented:
I think ur question is similar to
searching words in Dictionary.
I would also like to know the answer.
0
Ernest022699Commented:
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."?
0
ozoCommented:
How do you decide on your branches?
What information do you recieve when you guess?
0
rbrCommented:
Pls give more info what you want to do exactly!.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.