Разделяй и властвуй (англ. divide and conquer) — это принцип разработки алгоритмов, при котором задачу разбивают на две или более подзадачи того же типа, но меньшего размера. Их комбинируют так, чтобы в результате получить ответ к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными — базовыми.
Стратегия «разделяй и властвуй» работает так:
1 Шаг. Определяем простейший случай — базовый.
2 Шаг. Находим способ свести задачу к базовому случаю.
Рассмотрим пример: Имеется массив чисел. Нужно просуммировать все его элементы и вернуть сумму.
1 Шаг. Определим базовый случай — массив, состоящий из нуля элементов или из одного элемента. Суммой элементов таких массивов будет 0 и значение элемента соответственно.
2 Шаг. Задачу можно разбить так: результат равен сумме первого элемента и сумме всех оставшихся элементов. Сумму оставшихся элементов будем искать, применяя этот принцип к массиву оставшихся элементов.
Phyton:
Аналогично можно посчитать количество элементов в списке. Базовый случай — список пуст. Подзадача — результат равен сумме 1 и результату применения этого принципа к массиву, состоящему из всех элементов кроме первого.
Phyton:
Наибольшее число в списке ищем так: базовый случай — список состоит из одного числа. Подзадача: сравним первое число в списке с результатом применения этого принципа к списку оставшихся элементов.
Python: