ИНФОРМАТИКА ЗФТШ КАК РЕШАТЬ Вовочке надо построить забор из досок длиной в 20 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать з или 7 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.

Предыдущий
вопрос Следующий
вопрос

Чтобы решить задачу, можно использовать динамическое программирование.

Давайте обозначим количество способов построить забор длиной ( n ) метров как ( f(n) ). Условия задачи таковы:

На первом и последнем метре забора обязательно должны быть доски.Вовочка может пропустить 0, 2 или 7 метров подряд, но не более.

Мы можем разбить задачу на подзадачи, основываясь на том, сколько метров забора уже построено.

РекурсияЕсли на первом метре уже есть доска, то мы можем рассмотреть следующее:
Если Вовочка прибивает доску на следующий метр (это метр 2), значит, для остального забора длиной ( n - 2 ) способов будет ( f(n - 2) ).Если он пропускает 2 метра (то есть забор с 2 по 3) и ставит доску на 4 метре, значит, для остального забора длиной ( n - 4 ) будет ( f(n - 4) ).Если он пропускает 7 метров (то есть забор с 2 по 8), тогда нам нужны ( f(n - 8) ).

Таким образом, у нас есть:

( f(1) = 1 ) (на 1 метре только 1 способ — доска).( f(2) = 1 ) (на 1 и 2 метре только 1 способ).( f(3) = 1 ) (доски только на 1 и 3 метрах).( f(4) = 2 ) (доски могут быть на 1, 2 и 4, или на 1 и 3).( f(5) = 3 ) (возможные сочетания: 1, 2, 3, 5; 1, 2, 4; 1, 3, 4).( f(6) = 4 ).( f(7) = 6 ).( f(8) = 7 )....

Теперь, чтобы вычислить ( f(n) ), мы можем использовать следующие рекуррентные соотношения:

[
f(n) = f(n - 1) + f(n - 2) + f(n - 7)
]

Инициализация

Определяем базовые значения:

( f(1) = 1 )( f(2) = 1 )( f(3) = 1 )( f(4) = 2 )( f(5) = 3 )( f(6) = 4 )( f(7) = 6 )( f(8) = 7 )Результат

Теперь вычислим ( f(20) ), используя динамическое программирование и заполнив массив ( f ) для всех значений до 20:

Программируем рекуррентную формулу от 1 до 20, сохраняя значения в массиве.Выведем значение ( f(20) ).

В итоге, этот подход позволяет нам подсчитать количество способов построить забор длиной в 20 метров, с учетом всех условий, используя методы динамического программирования.