Оценка сложности алгоритма

• Задача «платная лестница» (см. домашнее задание):

  • Решение полным перебором (крайне неэффективное, ~n!)

  • Решение с помощью обхода дерева (неэффективное, ~2^(n/2))

  • Решение на основании рекуррентного соотношения: f(n)=min(f(n-1),f(n-2)) (сложность ~n)

• Задача о стоимости транзитного проезда (см. домашнее задание):

  • Решение полным перебором (крайне неэффективное, ~n!)

  • Решение на основании транзитивности искомой функции (Алгоритм Флойда-Уоршелла, ~n²·log₂n)

Домашнее задание

1. Прочитать теоретический материл об алгоритме Флойда и динамическом программировании (см. ссылку на единственный PDF, «Теоретический материал: динамическое программирование»)

2. «Платная лестница» (MCCME) Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. Ршение: stairs.py

3. «Гвоздики» (MCME). В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна. Решение: pegsNropes.py

4. «Транзитный проезд». Дана таблица, содержащая стоимость проезда из города i в город k по N городам (необязательно симметричная). Проезд стоит от 1 до 1000р, если проезда нет, в таблице записано N**2*1000. Вычислить минимальную стоимость проезда из любого города в любой с учётом пересадок.

Условные обозначения

• — тема по Linux

• ­— необязательная тема

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh