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

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

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

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

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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/2012-03-28 (last edited 2012-04-04 11:58:43 by FrBrGeorge)