Теория от примерни изпити
Динамично програмиране. Анализ и примери.
Формулиране на рекурентни уравнения: Определяне на отношенията между подзадачите и началната задача.
Идентификация на налагащи се подзадачи: Разделяне на главната задача на по-малки подзадачи.
Запазване на резултатите от подзадачите: Техниката на мемоизация се използва за запазване на вече изчислени резултати, които после могат да бъдат използвани за оптимизация.
Комбиниране на резултатите от подзадачите: Използване на резултатите от подзадачите за постигане на резултата на главната задача.
Пример за динамично програмиране може да бъде намирането на най-дългата нарастваща подредица (LIS - Longest Increasing Subsequence) в даден масив.
def lis(arr):
n = len(arr)
lis_lengths = [1] * n
for i in range(1, n):
for j in range(0, i):
if arr[i] > arr[j] and lis_lengths[i] < lis_lengths[j] + 1:
lis_lengths[i] = lis_lengths[j] + 1
return max(lis_lengths)
arr = [10, 22, 9, 33, 21, 50, 41, 60]
result = lis(arr)
print("Най-дългата нарастваща подредица е:", result)
Сподели с приятели: |
