Лабораторная работа № 7. Рекуррентные соотношения и динамическое программирование

Теоретические сведения

Соотношения, связывающие одни и те же функции, но с различными аргументами, называются рекуррентными соотношениями.

Значение \(i\)-го члена последовательности, заданной через рекуррентное соотношение можно вычислить с помощью итерационного или рекурсивного алгоритмов.

Рассмотрим пример рекуррентного соотношения: \[ F(i) = i \cdot F(i-1)+1 \] при этом \(F(0)=1\).

Рассчитаем элемент последовательности для \(i=4\). Для этого необходимо вычислить значения элементов с 1 по 4. Начинаем расчёт с 1, так как для \(i=0\) значение рекурренктного выражения уже определено по условию:

Задания для самостоятельной работы

Задание 1. Можно ли получить сумму? ДП (sam01.py)

Дан список целых неотрицательных чисел lst. Определить, можно ли получить число s путём сложения чисел в списке lst. Каждое число в списке можно использовать неограниченное количество раз.

Реализуйте решение задачи, описав функцию can_sum(s, lst), которая возвращает значения логического типа.

Пример работы функции:

can_sum(7, [5, 3, 4]) -> True
can_sum(8, [5, 7]) -> False
can_sum(0, [1, 2]) -> True

Блок-схема функции показана на рисунке:

Рисунок 1

🖈

Для записи решения используйте следующий шаблон кода:

def can_sum(s, lst):
    A = [False] * (s + 1) # заполнение списка A
    # реализуйте следующие инструкции по блок-схеме


# не редактируйте следующий код
print(can_sum(7, [5, 3, 4]))
print(can_sum(8, [5, 7]))
print(can_sum(0, [1, 2]))

Задание 2. Можно ли получить сумму? Рекурсивное решение (sam02.py)

Запишем решение предыдущей задачи через рекурсивную функцию.

В новом файле реализуйте рекурсивную функцию can_sum(s, lst) согласно следующей блок-схеме:

Рисунок 2

Для записи решения используйте следующий шаблон:

def can_sum(s, lst):
    # запишите код согласно блок-схеме


# не редактируйте следующий код
print(can_sum(7, [5, 3, 4]))
print(can_sum(8, [5, 7]))
print(can_sum(0, [1, 2]))

Задание 3. Вычисление значения рекуррентного выражения

Вычислите элемент последовательности, заданной с помощью рекуррентного соотношения для \(i=5\). Запишите результат вычисления промежуточных значений в таблицу.

\[ F(i)=F(i-1)+F(i-2)\ mod\ 2 \]

где \(F(0)=1, F(1)=2\).

\[ F(i)=F(i-1)^2+1 \]

где \(F(0)=2\).

\[ F(i)=F(i-1)\ div\ F(i-2)+1 \]

где \(F(0)=1, F(1)=2\).

\[ F(n)=(F(i-1) + F(i-2))\ div\ 2 \]

где \(F(0)=1, F(1)=3\).

\[ F(i)=F(i-1)\ mod\ F(i-2) \]

где \(F(0)=1, F(1)=3\).

\[ F(i)=-1^{F(i-1)}\cdot F(i-1) \]

где \(F(0)=2\).

\[ F(i) = F(i-1) + F(i-2) \cdot F(i-3) \]

где \(F(0) = 1, F(1) = 1, F(2) = 1\).

\[ F(i)=F(i-1)+F(i-2)\ mod\ 2 \]

где \(F(0)=1, F(1)=2\).

\[ F(i)=F(i-1)^2+1 \]

где \(F(0)=2\).

\[ F(i)=F(i-1)\ div\ F(i-2)+1 \]

где \(F(0)=1, F(1)=2\).

\[ F(n)=(F(i-1) + F(i-2))\ div\ 2 \]

где \(F(0)=1, F(1)=3\).

\[ F(i)=F(i-1)\ mod\ F(i-2) \]

где \(F(0)=1, F(1)=3\).

\[ F(i)=-1^{F(i-1)}\cdot F(i-1) \]

где \(F(0)=2\).

\[ F(i) = F(i-1) + F(i-2) \cdot F(i-3) \]

где \(F(0) = 1, F(1) = 1, F(2) = 1\).

Задание 4. Итерационный алгоритм (sam04.py)

Напишите функцию calc(n) с помощью которой можно рассчитать n-ый элемент последовательности, заданной рекуррентным соотношением для вашего варианта. Для хранения уже вычисленных элементов используйте список.

Шаблон функции:

def calc(n):
    # содержимое функции

Чтобы создать список из необходимого количества элементов используем операцию умножения:

F = [0] * (n + 1)

Получим список из n+1 элемента.

Запишите в созданный список начальные значения. Например, если \(F(0)=1\), то F[0] = 1.

Чтобы заполнить список элементам последовательности, запустите цикл for начиная с первого i для которого не определено конкретное значение. Например, если дано \(F(0) = 1\), значит первое значение переменной цикла должно быть равно 1, ведь для \(i=0\) значение уже должно быть занесено в список. Последнее значение переменной цикла равно n+1.

В теле цикла запишите с помощью синтаксиса Python рекуррентное выражение для вашего варианта. В конце тела функции нужно вернуть n-ый элемент из списка F.

# многоточие в шаблоне замените на необходимые значения самостоятельно

def calc(n):
    F = [0] * (n + 1) # заполнение списка нулями
    # запишите в F начальные значения
    # цикл для вычисления остальных элементов списка
    for i in range(..., ...):
        F[i] = ...
    return ...

# замените многоточие вызовом функции для n = 5
print(...)

Задание 5. Рекурсивный алгоритм (sam05.py)

Напишите рекурсивную функцию F(n) с помощью которой можно рассчитать n-ый элемент последовательности, заданной рекуррентным соотношением для вашего варианта.

Шаблон функции:

def F(n):
    # содержимое функции

Количество базовых случаев рекурсии будет зависеть от количества начальных значений выражения, заданных явно. Например, если \(F(0)=1\) а \(F(1)=2\), у функции будет два базовых случая:

if n == 0:
    return 1
elif n == 1:
    return 2

После базовых случаев, функция F() должна возвращать результат вычисления рекуррентного выражения.

Задание 6*. Поле с препятствиями (sam06.py)

Шаблон решения

Решение данной задачи запишите в файле sam06.py. Шаблон содержит тестовые данные и вспомогательную функцию print_grid(p) для форматированного вывода поля.

Робот движется по клеткам поля 🔲 размером 4x4. Он начинает своё движение в верхнем левом углу и движется в нижний правый угол поля. Робот может двигаться только вниз или вправо. Некоторые клетки поля - непроходимы 🔵 и робот не может на неё переместиться.

Напишите функцию grid(p) которая принимает на вход список списков p. Все элементы списка равны 0, за исключением тех клеток поля что не проходимы для робота. В этих клетках хранится значение -1.

Пример списка:

f1 = [
    [0, 0,-1, 0],
    [0, 0,-1, 0],
    [0,-1, 0, 0],
    [0, 0, 0, 0],
]

Пример вывода при правильном решении задачи:

🔲🔲🔲🔲
🔲🔲🔲🔲
🔲🔲🔲🔲
🔲🔲🔲🔲
Ожидаемый ответ: 20, полученный ответ: 20
🔲🔲🔵🔲
🔲🔲🔵🔲
🔲🔵🔲🔲
🔲🔲🔲🔲
Ожидаемый ответ: 1, полученный ответ: 1
🔲🔲🔲🔲
🔲🔲🔲🔲
🔲🔲🔲🔵
🔲🔲🔵🔲
Ожидаемый ответ: 0, полученный ответ: 0
🔲🔲🔲🔲
🔲🔲🔲🔲
🔲🔵🔵🔲
🔲🔲🔲🔲
Ожидаемый ответ: 5, полученный ответ: 5

Алгоритм решения во многом повторяет решение аналогичной задачи из лекции. Подумайте, что следует делать с клетками, в которых хранится значение -1.

Для прохода по двумерному списку понадобится два цикла for: один для строк, другой - для столбцов. Проследите, чтобы переменные циклов не выходили за размеры списка.

Клетки в которых хранится значение -1 необходимо пропускать и не изменять, если они окажутся по соседству с обычными клетками.