Subj : Re: Data Structure Problem
To   : comp.programming
From : Joe Seigh
Date : Tue Aug 09 2005 07:43 am

Joy wrote:
> 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.
> 
> 
Well, get a piece of graph paper and draw the solution.  Every time
you reverse direction move down one row, e.g.

# direction reverses
0                         .
1                         >.
2                        .<<
3                        >>>.

You should see a pattern emerge.  Keeping track of where you are is your
job.

You could optimize this somewhat by making, say, 10 moves in one direction
before going back and trying the same number of moves in the other direction.
Of course once you find a shop, you need to check the other direction to
verify the shop is nearer since you're moving 10 units at a time so there's
a trade off on the number of moves you make vs. average expected distance
to the nearest shop.

                       
> 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.

It becomes a random walk or Markov chain I would guess.



-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.