Облако знаний. Динамическое программирование. Подсчёт количества вариантов (Паскаль). Информатика. 9 класс

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

Динамическое программирование — метод решения задач путём составления последовательности из подзадач:
- первая подзадача имеет простое решение;
- последний элемент этой последовательности — это исходная задача;
- каждая подзадача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами.
Отличия динамичного программирования от использования рекурсивных функций:
- промежуточные значения вычисляются в цикле и сохраняются в списке;
- список заполняется от меньших значений к большим;
- сложность алгоритма существенно ниже.
Пример. Кузнечик сидит в клетке № 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-й клетки

Было полезно?