Wednesday, June 21, 2006
treasure problem[S]
you are in 2d space and you may call you original location as (0,0).I shall tell you at what dist you are from the treasure, but not the direction.you have to guess where the treasure is and you will be transfered to that point.if you find the treasure there well and good.else I shall tell you the dist again.this constitutes one move.write an algorithm to find out the treasure.prove that in worst case you can do it in 3 moves.[S]
Subscribe to:
Post Comments (Atom)
2 comments:
If treasure is at (x,y), we have two unknowns. D0*D0 = x*x+y*y, D1*D1 = (x-x1)*(x-x1)+(y-y1)*(y-y1) and D2*D2 = (x-x2)*(x-x2)+(y-y2)*(y-y2) will be known in the worst case, where (x1,y1) and (x2,y2) are positions of guesses. Solving first two might give a pair of solutions (quadratic eqns), so in the worst case we need the third eqn for a single solution.
you are correct, Sir.
Post a Comment