Учебники

Питон — разделяй и властвуй

Декабрь 19, 2018

При подходе «разделяй и властвуй» имеющаяся проблема разбивается на более мелкие подзадачи, а затем каждая проблема решается независимо. Когда мы продолжаем делить подзадачи на еще более мелкие подзадачи, мы можем в конечном итоге достичь стадии, когда больше деление невозможно. Эти «атомарные» наименьшие возможные подзадачи (дроби) решены. Решение всех подзадач в конечном итоге объединяется, чтобы получить решение исходной задачи.

Разделяй и властвуй

В целом, мы можем понять подход « разделяй и властвуй» в трехэтапном процессе.

Разделить / Перерыв

Этот шаг включает разбиение проблемы на более мелкие подзадачи. Подзадачи должны представлять часть первоначальной проблемы. Этот шаг обычно использует рекурсивный подход для разделения проблемы до тех пор, пока никакая подзадача не станет более делимой. На этом этапе подзадачи приобретают атомарный характер, но все же представляют некоторую часть актуальной проблемы.

Покори / Решить

Этот шаг получает множество мелких подзадач, которые необходимо решить. Как правило, на этом уровне проблемы считаются «решенными» сами по себе.

Слияние / комбинирование

Когда меньшие подзадачи решены, этот этап рекурсивно объединяет их, пока они не сформулируют решение исходной задачи. Этот алгоритмический подход работает рекурсивно, а этапы завоевания и объединения работают так близко, что они выглядят как единое целое.

Примеры

Следующая программа является примером подхода программирования « разделяй и властвуй», где бинарный поиск реализован с использованием python.

Реализация бинарного поиска

В бинарном поиске мы берем отсортированный список элементов и начинаем искать элемент в середине списка. Если значение поиска совпадает со средним значением в списке, мы завершаем поиск. В противном случае мы исключаем половину списка элементов, выбирая, следует ли перейти к правой или левой половине списка, в зависимости от значения искомого элемента. Это возможно, поскольку список отсортирован, и это намного быстрее, чем линейный поиск. Здесь мы разделяем данный список и побеждаем, выбирая правильную половину списка. Мы повторяем этот подход, пока не найдем элемент или не сделаем вывод об его отсутствии в списке. 

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Когда приведенный выше код выполняется, он дает следующий результат:

128
Share: