Сценарии в Linux; использование рекурсии; элементы динамического программирования
- Разбор Д/З
- Создание собственной программы
Исполняемые объекты (программы и сценарии): Переменные в shell; PATH; .bash_profile: PATH=$PATH:$HOME/bin
ls -l, chmod +x
- shebang
- Рекурсия
- Вложенные пространства имён, потребление памяти
- ⇒ условия использования и неиспользования
- рекурсивные вызовы ⇔ общий код + стек состояний
- (если успеем) пример преобразования исходного кода
- Разбор задачи «Платная лестница-1/2»:
- неэффективное рекурсивное решение и его анализ
- решение методом динамического программирования
- (если успеем) в т. ч. «неправильное» рекурсивное
- Введение в динамическое программирование: определение подзадач и их зависимостей
Домашнее задание
Прочитать о динамическом программировании в Википедии В частности, про числа Фибоначчи
- Input:
Наступить на k-ю ступень лестницы A стоит Ak монет. Ввести через запятую «цены» ступеней A, и на следующей строке — ширину шага S (все числа натуральные) и вывести минимальную стоимость пути с земли до последней ступени (на которую наступать обязательно), при условии, что идти можно только вверх и перешагивать можно не более, чем через S-1 ступень.
Output:5, 3, 6, 1, 1, 2, 3, 4, 7, 5, 5, 7, 1, 1, 4, 6, 3, 4, 7, 4, 2 4
14
(FibTail) Последние цифры большого числа Фибоначчи
Input:Последовательность чисел Фибоначчи определяется следующим образом: F0 = F1 = 1, Fn+1 = Fn+Fn-1. Ввести N (возможно, довольно большое) и вывести последнюю цифру N-го числа Фибоначчи.
Output:1234567
3
(ReqSum) Сумма подпоследовательности
Input:Ввести число N, а на следующей строке — последовательность натуральных чисел через запятую. Проверить, является ли N суммой не более, чем 10 каких-либо элементов последовательности, и вывести YES или NO в зависимости от результата.
Output:21 1,2,3,4,5,6,7,8,9,19,20,30,40
YES
Условные обозначения
- — тема по Linux
— тема повышенной сложности - — теоретическое задание
— тема для самостоятельного изучения