Рекурсия и динамическое программирование
Выбери формат для чтения
Загружаем конспект в формате docx
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Конспект лекции 17
Рекурсия и динамическое программирование
Рекурсия – это способ решения задачи через вызов от задач аналогично исходных элементов, но меньший по масштабу.
Крайний случай – это способ решения самых простых задач, где не требуют вызов от всех задач.
Факториал является тем случаем, где не надо использовать рекурсию:
1)
Реализации:
1)
Функция факториала, в результате является целое число. Если у меня крайний случай, то возврат на 1, а иначе- возврат на f(n-1) * n
def f(n : int) int:
if n == 0:
return 1
elif n>0:
return f(n-1) * n
Скорость вычисления факториала будет прямопропорциональному числу n, которое мы считаем факториал.
2)
В чем состоит динамическое программирование?
Я создаю массив со значениями функции. Я заложу значение функции 1 и повторю n+1 раз, чтобы заривезировать память под массив. Динамическое программирование состоит в том, что расширяет наши знания по значениях функции. Далее запускается цикл, начиная от 1 до n+1 включительно. Потом мы распечатываем данные на экран.
f = [1] + [Nore] * n
for i in range ( 1 , n+1):
f[i] = f[1-1] * i
print(f[n])
2)
Реализации:
1)
Мы оформляем функцию насчет расширения значений функции.
Крайний случай: утверждаем, что число n больше или равно 0.
Начинаем с выделением памяти, это будет массив. Мы потом заревезируем память. Я не хочу создавать пустой список или список содержащий только 0 и 1. Остальное аллоцировать в процессе последовательности. Далее в циклах мы расширяем знания значений функции.
def fib2(n : int) int:
assert n >= 0
fib = [Nore] * (n+1)
fib [:2] = [0,1]
for k in range (2, n+1):
fib[k] = fib[k-1] + fib[k-2]
return fib[n]
2)
Сначала оформляет функцию фибаначе, где содержатся целые числа. Крайний случай: утверждаем, что число n больше или равно 0. Теперь мы имеет право написать условие: n меньше или равно 1.
F = [Nore] * 10000
def fib(n : int) int:
assert (n>=0 and n<10000)
if F[n] is Nore:
if n<=1:
F[n] = n
else:
F[n] = fib(n-1) + fib(n-2)
return F[n]
Задача о рюкзаке
N штук
- количество выборок предметов
Асимптотика
Полный перебор - O()
Жадный алгоритм:
M = 3 + 5 = 8
V = 6 + 5 = 11
Дискретная задача о рюкзаке
F(i, k) – максимальная стоимость предметов, которая помещается в рюкзак ёмкости k, при этом можно использовать только первые i предметы.
Реализация:
F = [[0]*(N+1) for I in range (M+1)]
for i in range (1, N+1):
for k in range (1, M+1):
if m[1] <= k:
F[k][i] = max(F[k][i-1], v[i] + F[k-m[i]][i-1])
else:
F[k][i] = F[k][i-1]
F[M][N] - ответ
