Различия между версиями 4 и 5
Версия 4 от 2014-11-19 19:21:20
Размер: 2330
Редактор: FrBrGeorge
Комментарий:
Версия 5 от 2014-11-21 14:29:45
Размер: 2374
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 29: Строка 29:
  1. /!\ задача на рекурсию   1. <<HomeWork(ejvmsh:,ReqSum,Сумма подпоследовательности)>>

Сценарии в Linux; использование рекурсии; элементы динамического программирования

  • Разбор Д/З
  • Создание собственной программы
    • {o} Исполняемые объекты (программы и сценарии):

      • Переменные в shell; PATH; .bash_profile: PATH=$PATH:$HOME/bin

      • ls -l, chmod +x

      • shebang
  • Рекурсия
    • Вложенные пространства имён, потребление памяти
    • ⇒ условия использования и неиспользования
    • рекурсивные вызовы ⇔ общий код + стек состояний
      • (если успеем) пример преобразования исходного кода
  • Разбор задачи «Платная лестница-1/2»:
    • неэффективное рекурсивное решение и его анализ
    • решение методом динамического программирования
      • (если успеем) в т. ч. «неправильное» рекурсивное
  • Введение в динамическое программирование: определение подзадач и их зависимостей

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

  1. {i} Прочитать о динамическом программировании в Википедии

  2. (PaidStairs) Платная лестница

    Наступить на k-ю ступень лестницы A стоит Ak монет. Ввести через запятую «цены» ступеней A, и на следующей строке — ширину шага S (все числа натуральные) и вывести минимальную стоимость пути с земли до последней ступени (на которую наступать обязательно), при условии, что идти можно только вверх и перешагивать можно не более, чем через S-1 ступень.

    Input:

    5, 3, 6, 1, 1, 2, 3, 4, 7, 5, 5, 7, 1, 1, 4, 6, 3, 4, 7, 4, 2
    4
    Output:

    14
  3. (FibTail) Последние цифры большого числа Фибоначчи

    Последовательность чисел Фибоначчи определяется следующим образом: F0 = F1 = 1, Fn+1 = Fn+Fn-1. Ввести N (возможно, довольно большое) и вывести последнюю цифру N-го числа Фибоначчи.

    Input:

    1234567
    Output:

    3
  4. <<HomeWork(ejvmsh:,ReqSum,Сумма подпоследовательности)>>

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

  • {o} — тема по Linux

  • <!> ­— тема повышенной сложности

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

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


CategoryClass CategoryVmsh

LecturesVMSH/Python/2014-11-21 (последним исправлял пользователь FrBrGeorge 2014-11-21 14:30:06)