Data Structure Problem

[Joy]

Hi,
I have a problem in data structures which most of the people find a
homework but that it is and I am sorry for that.
I am stuck in this one .Please try to help me , just provide me the
outline how to analyse this problem.
Question : A man Joe has a habbit of eating pancakes & driving
bikes.Once he went for outside by his bike,now he is EXACTLY IN THE
MIDDLE OF A ROAD his stomach is crying for pancakes and also his
contact lenses are full of dirt.Now HE CANNOT SEE A PANCAKE SHOP UNTILL

HE REACH THE PANCAKE SHOP EXACTLY BEFIRE IT.
Now please provide me the algorithm for finding the pancake shop which
is nearer to JOE & also tell me how can I calculate time and space
complexity.
Note: Information given as if he goes to the right side it is
considered as 1unit,2unit....and son on and if he chooses left then
-1unit,-2unit...and so on.
II)Second part of the problem says that if Joe wants to flip a coin for

,in which direction(left or right) he has to move.
Then what happens to the code/algorithm.
left<---- ------>right
Example:----------------------**---------------------------
Road (Joe)in the middle of the road.
------------------------------**--------------------
Thanks
Paul.

[Karl Heinz Buchegger]

Joy wrote:

HE REACH THE PANCAKE SHOP EXACTLY BEFIRE IT.
Now please provide me the algorithm for finding the pancake shop which
is nearer to JOE

Well, how would you do it if you were Joe?

One of the secrets of programming is that you can't
write a program until you are able to solve the problem
by yourself.

I would do: Choose one direction. Walk into that direction
until either: the road ends or a shop is reached.
Turn around and return to the starting place.
Then walk in the other direction until either: the
road ends or a shop is reached.
Turn around, walk back to the starting point and make a
decission:
If 2 shops were reached then compare the distances and
choose the nearer one. If only one shop was reached, well,
take it and be happy.
That would be the overall strategy in order to solve that problem,
although I admit I would take the first shop I reach and would not
search for another one. But this is a different story and that
is not what the assignment asks for.

Another possibility would be:
turn one step to the left
is there a shop? if yes: goal reached
if no: turn around and make 2 steps to the right
is there a shop? if yes: goal reached
if no: turn around and make 3 steps to the left
is there a shop? if yes: goal rached
if no: turn around and make 4 steps to the right
is there a shop? if yes ....
and so on, and so on until both ends of the road have been
reached.

The ides behind all this is to make a pattern where you
investigate in alternate directions from the starting point

starting position *
try 1 to the left *|
try 1 to the right .|*
try 2 to the left *.|.
try 2 to the right ..|.*
try 3 to the left *..|..
try 3 to the right ...|..*
try 4 to the left *...|...
try 4 to the right ....|...*
..
..
..

so you know that the shop you find first must also be the nearest
one (measured from the starting position), because if there is a
nearer one, you would have discovered it in a previous step.

Or you can do ....
Well, think up a different strategy and try it.
Coming up with clever strategies is half of the fun in programming.

--
Karl Heinz Buchegger
kb******@gascad.at