Click here to Skip to main content
15,899,679 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Let x1< x2 < . . . < xn be real numbers representing coordinates of n villages located along a straight road. A post office needs to be built in one of these villages.

a) Design an efficient algorithm to find the post-office location minimizing the average distance between the villages and the post office.

What I have tried:

I'm trying to figure out how design it but i'm so confused. Can anyone help??
Posted
Updated 1-May-18 12:30pm
Comments
Maciej Los 1-May-18 14:26pm    
There's one problem... If you would like to write efficient algorithm, you need to know how many cities have to be around post office...

BTW: i'd look at moving average.

This is your homework, so I'll give you no code!

Start by thinking how you would do it manually. Assume you had four villages, and work out where you would place it.
How would you do that manually? Well, you'd start by assuming it was in Village 1, then work out the distance to each other village. Take the average of those distances.
Then do the same for Village 2, Village 3, and Village 4 - you now have four average distances and can work out which is the lowest.
That's the village where you put your post office!

Now start thinking about how you would automate that process, and then start to think about implementing it.
 
Share this answer
 
Quote:
I'm trying to figure out how design it but i'm so confused.

No! What you are doing is trying to magically guess the design. Unfortunately, magic works only for Jedi knights.

The only way to go is with a sheet of paper , pencil and solve the problem by hand.
As you need to understand the maths, try to put the post office in every village and get the score for each.
Try again with different sets of villages, make a drawing of positions of villages, see if you find a method that is more efficient.
The 'try every villages' is 'brut force' method, sometimes, it is the best.

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900