 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Разделяй и властвуй
|
|
Последовательность разделяй и властвуй использует рекурсию, чтобы решать проблемы, "деля" задачу на меньшие подзадачи. Base case рекурсии решает группу самых маленьких подзадач. "Властвовать" часть этой проблемы, которая происходит когда метод комбинирует эти решения создавая решение исходной проблемы.
Рисунок 1 Разделение проблемы
Обычно, алгоритмы «разделяй и властвуй» используют два вызова рекурсивной функции. Наличие двух рекурсивных вызовов непрерывно делит пространство задач на две части. Рисунок 1 иллюстрирует типичный шаг "дележа", который использует два рекурсивных вызова. Когда рекурсия достигает base case, подзадача решается непосредственно. Решения этих подзадач объединяются вместе (поскольку рекурсия раскручивается), и в конечном счете обеспечивают решение исходной проблемы. Рисунок 2 показывает решенные подзадачи, объединенные в решение для исходной проблемы.
Рисунок 2 объединенное решение
Рассмотрим проблему вычисления суммы квадратов диапазона целых чисел. Мы можем применить разделение и использовать подход, чтобы уменьшать диапазон непрерывно, пока мы не достигаем подзадачи размера, который легко вычисляется. Листинг 1 содержит исходный код для этого рекурсивного, основанного алгоритма разделяй и властвуй.
| 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 1 Finding the sum of the squares of a range of integers |
Другой пример простого и эффективного алгоритма разделяй и властвуй, приведен в листинге 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 2 Finding the smallest element in an array |
Функция find_smallest определяет самый маленький элемент, сохраненный в массиве, непрерывно деля массив на два мелких кусочка. Когда эти части являются достаточно маленькими, что они только содержат один элемент, алгоритм тогда сравнивает элементы, сохраненные в двух частях, и возвращает меньшие из этих двух элементов.
Дата публикования: 2014-12-08; Прочитано: 220 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
