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

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

  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. (ReqSum) Сумма подпоследовательности

    Ввести число N, а на следующей строке — последовательность натуральных чисел через запятую. Проверить, является ли N суммой не более, чем 10 каких-либо элементов последовательности, и вывести YES или NO в зависимости от результата.

    Input:

    21
    1,2,3,4,5,6,7,8,9,19,20,30,40
    Output:

    YES

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


CategoryClass CategoryVmsh