Pergunta

Let's assume I am trying to find a hidden treasure.

The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is an integer). In order to find the treasure I have to take with me a detector. The detector can spot the treasure only if it is above it.

My starting position is the 0 point and I can move back and front until I cross the treasure, so that my detector can track it. I am always moving on the integer line. Which is the most efficient way to move through the axis in order to track the treasure?? I have to find an algorithm that allows me to find the treasure by covering a distance $O(|x|)$

My approach: After some consideration, I think that the most efficient way to find the treasure is the following: Starting from 0 I move front until I reach number $2$. Then I move back until I reach number $-2^2$. Then I move front until I reach number $2^3$. Then I go back again until I reach number $-2^4$ and so on...

However, I am having difficulties on proving that there is a constant $c$ (for which I have to calculate an upper bound) so that my algorithm is going to help me find the treasure at $c |x|$ moves at most. Any help is much appreciated! Thanks in advance!

P.S. I am new at the computer science stack exchange so I am not sure about the tags. Correct them or add more if necessary.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top