CT240 lab8
http://geminga.it.nuigalway.ie/~gettrick/courses/CT240/labs/l8.html
-
For this lab you must submit a printout of all source code (python
files), and the result(s) of running the program on (a few)
test cases.
The source code must
be well presented (indenting, spaces, reasonable variable/function names,
etc.) and must include comments (as a rough guideline - aim to have nearly as
many comments as lines of code). Any questions asked should be answered on a plain sheet of paper.
-
The above material should be given to Paul or left in the cardboard box marked CT240 in the mail room (room IT415) on the 4th floor of the IT Building
before
the deadline of 5pm
Monday 10th. November 2008. You will lose 20% for each day
(or part of day) the lab is late. If you have a genuine reason for
submitting a late lab, please contact Paul before the lab
due date/time.
-
Plagiarism (the unattributed copying of work from other sources
(internet, fellow students,....)) will not be tolerated. Please see
http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students
_v4.pdf. You risk getting zero for your lab if it is found to be
plagiarized.
Consider the "shops" problem covered in lectures:
There are n businesses in a row on a street. Each one makes a yearly
profit (or loss), and we are given these numbers. Assume we can "buy"
or acquire these businesses essentially for free, but there is an
extra rule that any businesses we buy must neighbor one another
(i.e. must be in the same block). The block can be of any
size (including all n businesses, or block of size zero!). The puzzle is
to decide which businesses to buy, to obtain maximum yearly profit.
-
Write a program which "solves" this problem using the greedy
strategy
-
Write a program which solves this problem using the brute force
strategy
(Your programs should state both which businesses to buy and
the resulting yearly profit.)
In both cases, you should read in the data (list of numbers) from the user,
with individual numbers separated by e.g. commas.
Run each of your programs on the following input, and submit with the lab report
the result obtained:
-
87,34,-29,3,-4,65,2,18,-78,-37,-2,9,-5,62,3,31,-6,-28,30,21,24,19,-77,31,-2,50,60
-
17,34,-21,31,-4,55,2,18,-28,-87,-2,29,-9,-62,3,21,-61,-28,20,51,34,19,-17,31,-29,50,10
©
NUI, Galway