remarked a couple of publications that someday I would make some quick notes on the Divide and Conquer that is used in the field of programming. Well, I think the time has come.
Therefore, I warn you that today we go into the algorithmic design patterns - among which we find is the aforementioned Divide and Conquer -. D & C is an algorithmic paradigm of the family down strategies Top Down or . What does this mean? means that decompose the initial problem (hierarchically) into smaller subproblems to find it easier to solve. This implies the simplification problem and each subproblem at each decomposition, the different parts of the problem can be programmed to independently and the final program is structured modularly making it easier to read and maintain.
Summarizing all this, Divide and Conquer is a technique that solves a general problem by combining partial solutions of its subproblems . One note, the subproblems must be independent of one another to achieve an efficient outcome.
This strategy is solved by the following organization:
1. Divide : the stage where the problem is divided into one or more subproblems.
2. Conquer: is the stage where each case (subproblem) is solved independently.
3. Combination: is the stage that combines the solutions of the subproblems to obtain the general solution.
usually implemented using recursion for each subproblem. This does not mean that all problems that may have a recursive algorithm have to belong to those that can be solved by Divide and Conquer. As an example, the Fibonacci series not be a good example of this strategy since the subproblems are not independent of each other, but instead can be very useful in management strategies (mergesort, or basic sorting QuickSort) .
Here you have a pattern image of the UML template method. In another moment I'll upload a sample code, I thought I had one on the computer but I have not found. I hope you like ever help.
0 comments:
Post a Comment