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

ПредупреждениеНеобходимые файлы

Перед началом работы, cкачайте файл с заданиями, выполняемыми без компьютера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F = [0] * (n + 1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 4. Лестница (sam04.py)

Перед вами лестница с \(n\) ступеньками, где \(n>0\). Каждым шагом вы можете подниматься на одну или две ступеньки. Напишите функцию S(n) которая посчитает, сколькими способами можно подняться на n-ую ступеньку. Будем считать, что S(0) -> 1 и S(1) -> 1

Рассмотрим задачу для которой n=5. На ступеньку 1 можно подняться x способом. На ступеньку 2 можно подняться либо с нулевой, либо с первой ступеньки:

Значит, для вычисления S(2) нужно использовать следующее рекуррентное выражение: x S(2)=S(1)+S(0). В общем случае, для i ступенек получим выражение x S(i)=S(i-1)+S(i-2) .

Для решения задачи можем воспользоваться хранением решённых подзадач в списке размером n+1 где под индексом i будет храниться S(i):

Запишите код функции S(n) самостоятельно. Функция должна выводить на экран список с промежуточными вычислениями.

Примеры работы программы:

Количество ступенек: <{5}> ++enter++
[1, 1, 2, 3, 5, 8]
Ответ: 8
Количество ступенек: <{1}> ++enter++
[1, 1]
Ответ: 1
Количество ступенек: <{11}> ++enter++
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
Ответ: 144

Задание 5. Лестница с поломанными ступеньками (sam05.py)

Перед вами лестница с \(n\) ступеньками, где \(n>0\). Каждым шагом вы можете подниматься на одну или две ступеньки. Некоторые ступеньки сломаны, и вставать на них нельзя. Ступеньки с номерами \(0\) и \(n\) всегда целые. Напишите функцию broken_stairs(n, broken), где broken - список номеров сломанных ступенек. Функция должна посчитать, сколькими способами можно подняться на n-ую ступеньку. Будем считать, что для n=0 ответ всегда равен 1.

Функция должна выводить на экран список с промежуточными вычислениями. Используйте следующий шаблон кода:

def broken_stairs(n, broken):
    ... # решение задачи


# тестирование функции
print(broken_stairs(5, []))
print(broken_stairs(5, [2]))
print(broken_stairs(6, [3, 4]))

Пример работы программы:

[1, 1, 2, 3, 5, 8]
8
[1, 1, 0, 1, 1, 2]
2
[1, 1, 2, 0, 0, 0, 0]
0

Задание 6. Прыжки по камням (sam06.py)

Перед вами ряд камней, пронумерованных числами от \(0\) до \(n\), где \(n>0\). Вы стоите на камне \(0\). За один прыжок можно перепрыгнуть вперёд на любое количество камней от \(1\) до \(k\) включительно, где \(1 \le k \le n\). Напишите функцию stones(n, k), которая посчитает, сколькими способами можно добраться до камня с номером n. Будем считать, что до камня \(0\) можно добраться одним способом.

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

def stones(n, k):
    ... # решение задачи


# тестирование функции
print(stones(5, 2))
print(stones(5, 3))
print(stones(4, 1))

Пример работы программы:

8
13
1

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

УведомлениеШаблон решения

Решение данной задачи запишите в файле sam07.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 необходимо пропускать и не изменять, если они окажутся по соседству с обычными клетками.