Problem Decomposition
Definition
A BINDING is an association from a name to an object (value).
Definition
An ENVIRONMENT is a set of bindings.
Problem
A necklace is constructed from 20 blue beads and 14 red beads. Each blue bead costs $ 0.22. While each read bead costs $ 0.33. The total cost of the thread is $ 0.14 per inch, and 24 inches are required. What is the total cost of the materials for the necklace?
Definition
PROBLEM DECOMPOSITION is the problem solving strategy of decomposing a problem into a set of subproblems solving each of the subproblems, and then composing a solution to the original problem by exploiting the solutions to the subproblems.
Informal Solution Description
To determine the total material cost (that is to solve the problem) we need only use problem decomposition and solve the following subproblems:
- find the cost of blue beads
- find the cost of red beads
- find the cost of the thread
Sometimes problem decomposition is applied at many levels in solving a problem. In this case we can apply it to solving each of the subproblems.
We can find the blue bead cost by:
- determining the number of blue beads
- determining the cost of each blue bead
We can find the red bead cost by:
- determining the number of red beads
- determining the cost of each red bead
We can find the thread cost by:
- price per inch
- length of thread
Since we conceived of the solution in a ``top down'' manner we must code the solution using a ``bottom up'' manner.
Whenever you write programs in this class you must artfully name all values-within reason.
This is an example of a program written using problem decomposition.
? class ---- NecklaceApp
? program
/ /Determine the cost of the blue beads.
double costPerBlueBead = 0.22;
int nrBlueBeads = 20;
double blueBeadCost = costPerBlueBead * nrBlueBeads;
/ /Determine the cost of the read beads.
double costPerRedBead = 0.33;
int nrRedBeads = 14;
double redBeadCost = costPerRedBead * nrRedBeads;
/ /Determine the cost of the thread.
double costPerInchOfThread = 0.14;
doublelengthOfThread = 24.0;
double costOfThread = costPerInchOfThread *
lengthOfThread;
/ /Solve the original problem by making use of the
solutions to the three main subproblems.
double totalCost = blueBeadCost + redBeadCost +
costOfThread;
/ /Display the results.
IO.print (``Total cost of materials is ``);
IO.print (totalCost);
IO.println ();
|
The Environment
- costPerBlueBead - 0.22
- nrBlueBeads - 20
- blueBeadCost - 4.4
- costPerRedBead - 0.33
- nrRedBeads - 14
- redBeadCost - 4.62
- costPerInchOfThread - 0.14
- lengthOfThread - 24.0
- costOfThread - 3.36
- totalCost - 12.38
