Рекурсия и динамическое программирование

Конспект лекции 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] - ответ