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

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

  1. {i} Почитать о применении метода редукции («динамического программирования») на сайте MCCME

  2. Разобрать и написать решение задачи Платная лестница:

    • Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
      • любое эффективное
      • +с хранением только двух дополнительных значений F
      • +без хранения стоимости ступенек
  3. Решить задачу Ход конём:

    • Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз. Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

    • любое решение
    • решение эффективной редукцией
    • <!> решить задачу Ход конем - 2, в которой коню разрешено 4 хода из 8:

          -- -- -- --
         |  |  |  |1 |
          -- -- -- --
         |  |K |  |  |
          -- -- -- --
         |  |  |  |2 |
          -- -- -- --
         |4 |  |3 |  |
          -- -- -- --

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


CategoryClass CategoryVmsh