Page 82 - Bkhargava_-_Grokaem_algoritmy
P. 82
«Разделяй и властвуй» 81
Вспомните, как работает стратегия ~разделяй и властвуй•:
1. Определите простейший случай как базовый.
2. Придумайте, как свести задачу к базовому случаю.
«Разделяй и властвуй~ - не простой алгоритм, который можно применить
для решения задачи. Скорее, это подход к решению задачи. Рассмотрим
еще один пример.
[2f 4 [6 / Имеется массив чисел.
Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле
совсем не сложно:
def sum(arr):
total = 0
for х in arr:
total += х
return total
print sum{[l, 2, з, 4])
Но как сделать то же самое с использованием рекурсивной функции?
Шаr 1: определить базовый случай. Как выглядит самый простой массив,
который вы можете получить? Подумайте, как должен выглядеть про
стейший случай, и продолжайте читать. Если у вас будет массив с О или
1 элементом, он суммируется достаточно просто.
www.trk.kg
