Subj : Re: Data Structure Problem
To   : comp.programming
From : Joy
Date : Wed Aug 10 2005 08:48 am


Joe Seigh wrote:
> 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
Thanks Joe for your kind reply.
Regards
Paul
>
> When you get lemons, you make lemonade.
> When you get hardware, you make software.

.