рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Divide and Conquer

Divide and Conquer - раздел Философия, Recursive factorials Divide And Conquer Is A Problem Solving Technique That Utilizes Recurs...

Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the recursion solves the group of the smallest sub-problems. The "conquer" portion of this problem solving technique then combines these solutions to create the solution to the original problem.


Figure 1 Dividing a problem

Generally, divide and conquer algorithms utilize two recursive function calls. Having two recursive calls continually divides the problem space into two parts. Figure 1 illustrates a typical "divide" step that uses two recursive calls. When the recursion reaches the base case, the sub-problems are solved directly. The solutions to these sub-problems are then combined together (as the recursion unwinds) and eventually form the solution to the original problem. Figure 2 shows the solved sub-problems combined into a solution for the original problem.


Figure 2 The combined solution

Consider the problem of calculating the sum of the squares of a range of integers. We can apply the divide and conquer approach to reduce the range continually until we reach a sub-problem size that is easily calculated. Listing 1 contains the source code for this recursive, divide-and-conquer based algorithm.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: #include <iostream> #include <cstdlib>   using namespace std;   int ssq(int m, int n) {   if (m == n) { return m * m; // base case } else { int middle = (m + n) / 2; // recursive divide return ssq(m, middle) + ssq(middle + 1, n); } }   int main(int argc, char* argv[]) {   cout << "ssq(1,10) = " << ssq(1, 10) << endl;   return EXIT_SUCCESS; }
Listing 1Finding the sum of the squares of a range of integers

Another example of a simple and effective divide and conquer based algorithm appears in Listing 2.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: #include <iostream> #include <cstdlib>   using namespace std;   int find_smallest(int a[], int size) {   if (size == 1) { return a[0]; // base case } else {   // Search the first half of the array for the smallest element. int s1 = find_smallest(a, size / 2);   // Search the second half of the array for the smallest element. int s2 = find_smallest(a + size / 2, size - size / 2);   return (s1 < s2) ? s1 : s2; } }   int main(int argc, char* argv[]) {   int arr[] = {13, 19, 12, 11, 15, 19, 23, 12, 13, 22, 18, 19, 14, 17, 23, 21};   cout << "smallest: " << find_smallest(arr, 16) << endl;   return EXIT_SUCCESS; }
Listing 2Finding the smallest element in an array

Function find_smallest determines the smallest element stored in an array by continually dividing the array into two smaller pieces. When these pieces are small enough that they only contain one element, the algorithm then compares the elements stored in two pieces and returns the smaller of the two elements.

– Конец работы –

Эта тема принадлежит разделу:

Recursive factorials

Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Divide and Conquer

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

The Call Stack
The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pend

Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu

Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to

The Problem
A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each

The Solution
To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight q

The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято

Замена рекурсии
Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рек

Отслеживание в обратном порядке. Понятие
Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процес

Проблема
Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске т

Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, ко

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги