|
|
|
|
|
|
|
Figure 1-15
Divide and Conquer |
|
|
|
|
|
|
|
|
Another way to combine existing solutions is to merge them on a step-by-step basis. For example, to compute the average of a list of values, we must both sum and count the values. If we already have separate solutions for summing values and for counting values, we can combine them. But if we first do the summing and then do the counting, we have to read the list twice. We can save steps if we merge these two solutions: read a value and then add it to the running total and add 1 to our count before going on to the next value. Whenever the solutions to subproblems duplicate steps, think about merging them instead of joining them end to end. |
|
|
|
|
|
|
|
|
Mental Blocks: The Fear of Starting |
|
|
|
|
|
|
|
|
Writers are all too familiar with the experience of staring at a blank page, not knowing where to begin. Programmers have the same difficulty when they first tackle a big problem. They look at the problem and it seems overwhelming. |
|
|
|
|
|
|
|
|
Remember that you always have a place to begin solving any problem: Write it down on paper in your own words so that you understand it. Once you begin to try to paraphrase the problem, you can focus on each of the subparts individually instead of trying to tackle the entire problem at once. This process gives you a clearer picture of the overall problem. It helps you see pieces of the problem that look familiar or that are analogous to other problems you have solved. And it pinpoints areas where something is unclear, where you need more information. |
|
|
|
|
|
|
|
|
As you write down a problem, you tend to group things together into small, understandable chunks, which may be natural places to split the problem upto divide and conquer. Your description of the problem may |
|
|
|
|
|
