• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 250
  • Last Modified:

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
0
paulwhelan
Asked:
paulwhelan
1 Solution
 
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
 
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
Free tool for managing users' photos in Office 365

Easily upload multiple users’ photos to Office 365. Manage them with an intuitive GUI and use handy built-in cropping and resizing options. Link photos with users based on Azure AD attributes. Free tool!

 
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

Featured Post

Live webcast with Pinal Dave

Pinal Dave will teach you tricks to help identify the real root cause of database problems rather than red herrings. Attendees will learn scripts that they can use in their environment to immediately figure out their performance Blame Shifters and fix them quickly.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now