acrilas
asked on
[Algorithms] Finding numbers
Suppose x, y (distinct) belongs to a set of integers from 0 to n-1.
Consider a game bwetween players A and B. PLayer A keeps the 2 numbers x, y. B wants to find out x, y by asking questions.
a) Suppose A will reply either Yes or No. At least how many quetions B must ask to determine x, y?
My ans which i think is not correct: log (n) + log (n-1)
Any suggestions?
b) Suppose B can ask A in the following way:
B gives A a number r.
A tells B whether x > r, and whether y > r.
Hence for one question asked by B, there are 4 possible outcomes from A.
What's a good algorithm for B?
???
Consider a game bwetween players A and B. PLayer A keeps the 2 numbers x, y. B wants to find out x, y by asking questions.
a) Suppose A will reply either Yes or No. At least how many quetions B must ask to determine x, y?
My ans which i think is not correct: log (n) + log (n-1)
Any suggestions?
b) Suppose B can ask A in the following way:
B gives A a number r.
A tells B whether x > r, and whether y > r.
Hence for one question asked by B, there are 4 possible outcomes from A.
What's a good algorithm for B?
???
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
That, of course, should read:
so the number of *possible* valid answers is reduced by just 1.