Page 83 - Bkhargava_-_Grokaem_algoritmy

82 Глава 4. Быстрая сортировка

LJ О ЭЛЕМЕНТОВ =СУММА 'РА&НА О
БА.30ВЫ~
С.ЛУЧАР~ ' ЭЛЕМЕНТ = С.УММА 'РАВНА т
[1]

Итак, с базовым случаем мы определились.
Шаr 2: каждый рекурсивный вызов должен приближать вас к пустому мас­
сиву. Как уменьшить размер задачи? Один из возможных способов:

-
- 12

:::. 2+1Ф :12

В любом случае результат равен 12. Но во второй версии функции sum
передается меньший массив. А это означает, что вы сократили размер своей
задачи!

Функция sum может работать по следующей схеме:

ПОЛУЧИТЬ
список

"l ~
Если сnисок Ь П'РОТИ&НОМ СЛУЧАЕ 'РЕЗУЛЬ-
ПУСТ, 6Е'Р- пт 'РА6ЕН СУММЕ ПЕ'Р6Оrо
НУТЬ О ЧИСЛА 6 СПИСКЕ И СУММЫ
оспльноrо сnискА

www.trk.kg