Оценка сложности и выбор алгоритма
- Общие замечания: показательная сложность минимаксных задач общего вида и ненадёжность «жадных» алгоритмов
- Метод редукции (сведения задачи к серии подзадач меньшей сложности): условия применимости
Разбор задачи Платная лестница:
- «Тупой» перебор рекурсией: FMin(n)=min(FMin(n+1),FMin(n+2))
- Он же с кешированием FMin(k)
- Линейный алгоритм с хранением результатов: F[n]=min(F[n-1],F[n-2])
Домашнее задание
Почитать о применении метода редукции («динамического программирования») на сайте MCCME Разобрать и написать решение задачи Платная лестница:
- Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
- любое эффективное
- +с хранением только двух дополнительных значений F
- +без хранения стоимости ступенек
- Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
Решить задачу Ход конём:
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз. Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
- любое решение
- решение эффективной редукцией
решить задачу Ход конем - 2, в которой коню разрешено 4 хода из 8: -- -- -- -- | | | |1 | -- -- -- -- | |K | | | -- -- -- -- | | | |2 | -- -- -- -- |4 | |3 | | -- -- -- --2014-04-18-knight5.py (другой вариант)
Условные обозначения
— тема по Linux - — тема повышенной сложности
- — теоретическое задание
— тема для самостоятельного изучения