Информатика • 9 класс
280

Динамическое программирование. Подсчёт количества вариантов (Паскаль)

  • Динамическое программирование — метод решения задач путём составления последовательности из подзадач:
    • первая подзадача имеет простое решение;
    • последний элемент этой последовательности — это исходная задача;
    • каждая подзадача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами.
  • Отличия динамичного программирования от использования рекурсивных функций:
    • промежуточные значения вычисляются в цикле и сохраняются в списке;
    • список заполняется от меньших значений к большим;
    • сложность алгоритма существенно ниже.
  • Пример. Кузнечик сидит в клетке 1 и может прыгать вправо на 1 или 3 клетки. Подсчитайте количество разных способов, которыми он может добраться до клетки N.
  • Программный код (фрагмент основного алгоритма):
    for i := 1 to N do
    F [i] := 0; //заполняем массив начальными нулевыми значениями
    F [1] := 1; //единственный путь для исходной 1-й клетки
    F [2] := 1; // единственный путь для 2-й клетки
    F [3] := 1; // единственный путь для 3-й клетки
    for i := 4 to N do
    F [i] := F [I - 1] + F [I - 3];
    //в i-ю клетку можно попасть из (i-1)-й и (i-3)-й клеток
    writeln F [N]; //количество различных путей добраться до N-й клетки
Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»