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.

Aug 8 '05 #1

Subscribe Reply

1345

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

Aug 8 '05 #2

Similar topics

6471

What is the data structure & algorithm that is fastest searching & sorting.

by: yee young han | last post by:

I need a fast data structure and algorithm like below condition. (1) this data structure contain only 10,000 data entry. (2) data structure's one entry is like below typedef struct _DataEntry_ { char szInput; char szOutput; int iSum;

C / C++

5115

Multileval data structures, tie, and indirection

by: Da-Breegster | last post by:

Hi. I'm attempting to write a roguelike (think nethack, crawl, angband, tome, adom, and yes, I suppose even rogue) in Perl and I've ran into a problem regarding the data structure for the map and handling it easily. A map is one 2D level, a simple grid. Each tile on the grid will be a hash of data about the grid. The map object itself has other bits of data, so that's why I don't just make the object an anonymous array: $map->{Map} = {...

Perl

3869

statically allocated data structures source?

by: Thomas Paul Diffenbach | last post by:

Can anyone point me to an open source library of /statically allocated/ data structures? I'm writing some code that would benefit from trees, preferably self balancing, but on an embedded system that doesn't offer dynamic memory allocation (to be clear: no malloc, no realloc), and with rather tight memory constraints. Writing my own malloc to do dynamic allocation from some static pool isn't really an option, for various reasons, not...

C / C++

3197

data types question

by: theshowmecanuck | last post by:

As a matter of academic interest only, is there a way to programmatically list the 'c' data types? I am not looking for detail, just if it is possible, and what function could be used to accomplish it. For example: int main void() { while there are more data types { print next data type; }

C / C++

4794

initializing data at compile time

by: Bart Goeman | last post by:

Hi, I have a question about how to put redundant information in data structures, initialized at compile time. This is often necessary for performance reasons and can't be done at run time (data structures are read only) Ideally one should be able to put the redundant information there automatically so no mistakes are possible, but in a lot of case I see no way how to do it.

C / C++

4809

serializing an arbitrary data structure into a flat buffer (raw contiguousmemory block)

by: Alfonso Morra | last post by:

Hi, I am writing a messaging library which will allow me to send a generic message structure with custom "payloads". In many cases, a message must store a non-linear data structure (i.e. "payload") using pointers. Examples of these are binary trees, hash tables etc. Thus, the message itself contains only a pointer to the actual data. When the message is sent to the same processor, these pointers point to the original locations, which...

C / C++

1411

how to form queues for data storage and how to Handle the matching of the Responses

by: saleem | last post by:

Dear friends, I am working on the problem which deals with the data management of requests and how should we match the responses for the requests to compare the correct Response. my problem is like this, say I am intermediary node between "m" and "n" nodes . n nodes send any of the "p"type of requests to any one of the "m" nodes on the other side. I have to forward the requests to

C / C++

4931

Displaying data in datagrid problem

by: vinayak | last post by:

Hi I am displaying data in Datagrid in ASP.NET with Edit/Update functionality for each row. On the same page I have 2 Button controls which submits the request to server. These button controls are Web Control & not HTML control. One of these buttons whose title is Delete is added on the aspx page in design view & also I double clicked on this button in design view to get the onclick code for this button in the code behind page. & for...

ASP.NET

4282

Parsing a Section of Binary String Data!

by: zoltan | last post by:

Hi, The scenario is like this : struct ns_rr { const u_char* rdata; }; The rdata field contains some fields such as :

C / C++

3411

How to Automatically Update UI When Data Changes

by: Charles Law | last post by:

Here's one that should probably have the sub-heading "I'm sure I asked this once before, but ...". Two users are both looking at the same data, from a database. One user changes the data and commits it. How does the other user get the updated view without polling for changes? Is there some sort of callback mechanism that can be set up on the dataset or connection? TIA

.NET Framework

9803

What is ONU?

by: marktang | last post by:

ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...

General

10811

Problem With Comparison Operator <=> in G++

by: Oralloy | last post by:

Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...

C / C++

10560

The easy way to turn off automatic updates for Windows 10/11

by: Hystou | last post by:

Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...

Windows Server

10233

Discussion: How does Zigbee compare with other wireless protocols in smart home applications?

by: tracyyun | last post by:

Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...

General

7766

Access Europe - Using VBA to create a class based on a table - Wed 1 May

by: isladogs | last post by:

The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...

Microsoft Access / VBA

6966

Couldn’t get equations in html when convert word .docx file to html file in C#.

by: conductexam | last post by:

I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...

C# / C Sharp

5804

Windows Forms - .Net 8.0

by: adsilva | last post by:

A Windows Forms form does not have the event Unload, like VB6. What one acts like?

Visual Basic .NET

3993

How to add payments to a PHP MySQL app.

by: muto222 | last post by:

How can i add a mobile payment intergratation into php mysql website.

PHP

3088

Comprehensive Guide to Website Development in Toronto: Expert Insights from BSMN Consultancy

by: bsmnconsultancy | last post by:

In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

General