Галина Ивановна Шкатова

Алгоритмы «разделяй и властвуй» (декомпозиции)
АЛГОРИТМИЧЕСКИЕ СТРАТЕГИИ 

---

Пример: 
Пусть требуется вычислить сумму чисел:
Решение методом «грубой силы»: 
int Sum(int*a, int n) 
{ 
int S=0; 
for(int i=0; iS = S+a[i]; 
return S; 
} 
При 
решении методом декомпозиции 
исходная задача – «Сумма n элементов» разбивается на 
две суммы с числом элементов n/2: 
Каждая из сумм по той же схеме разбивается на 2 суммы и т.д., пока в очередной сумме не 
останется один элемент. Например: 
4+5+1+9+13+11+7 =(4+5+1)+(9+13+11+7) = [(4)+(5+1)]+[(9+13)+(11+7)] 
=[(4)+(5)+(1)]+[(9)+(13)]+[(11)+(7)] = 50 
Сумма сводится к сумме
, но с другим числом элементов – элемент рекурсии. 
int Sum(int*a, int ltft, int right) 
{ 
// left - левая граница индексов,right – правая граница 
индексов 
if(left==right) return a[left];//если один элемент 
int k = (r-left+1)/2;//значение среднего индекса 
return Sum(a,left, left+k-1) + Sum(a, left+k, right) ; 
} 
АЛГОРИТМИЧЕСКИЕ СТРАТЕГИИ 

---

Здесь в квадратных скобках указаны значения левых и правых индексов 
суммируемых элементов 
Структура рекурсивных вызовов для примера сложения:
АЛГОРИТМИЧЕСКИЕ СТРАТЕГИИ 

---

Примеры алгоритмов, основанных на методе «разделяй и 
властвуй» – декомпозиции: 

Сортировка слиянием. 

Быстрая сортировка. 

Бинарный поиск. 

Обход двоичного дерева. 

Решение задачи о поиске выпуклой оболочки. 

Умножение матриц методом Штрассена. 

И др. 
АЛГОРИТМИЧЕСКИЕ СТРАТЕГИИ 

---