ИНФОРМАТИКА ЗФТШ КАК РЕШАТЬ Вовочке надо построить забор из досок длиной в 20 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать з или 7 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.
ИНФОРМАТИКА ЗФТШ КАК РЕШАТЬ Вовочке надо построить забор из досок длиной в 20 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать з или 7 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Чтобы решить задачу, можно использовать динамическое программирование.
Давайте обозначим количество способов построить забор длиной n n n метров как f(n) f(n) f(n). Условия задачи таковы:
На первом и последнем метре забора обязательно должны быть доски.Вовочка может пропустить 0, 2 или 7 метров подряд, но не более.Мы можем разбить задачу на подзадачи, основываясь на том, сколько метров забора уже построено.
РекурсияЕсли на первом метре уже есть доска, то мы можем рассмотреть следующее:Если Вовочка прибивает доску на следующий метр этометр2это метр 2этометр2, значит, для остального забора длиной n−2 n - 2 n−2 способов будет f(n−2) f(n - 2) f(n−2).Если он пропускает 2 метра тоестьзаборс2по3то есть забор с 2 по 3тоестьзаборс2по3 и ставит доску на 4 метре, значит, для остального забора длиной n−4 n - 4 n−4 будет f(n−4) f(n - 4) f(n−4).Если он пропускает 7 метров тоестьзаборс2по8то есть забор с 2 по 8тоестьзаборс2по8, тогда нам нужны f(n−8) f(n - 8) f(n−8).
Таким образом, у нас есть:
f(1)=1 f(1) = 1 f(1)=1 на1метретолько1способ—доскана 1 метре только 1 способ — доскана1метретолько1способ—доска.f(2)=1 f(2) = 1 f(2)=1 на1и2метретолько1способна 1 и 2 метре только 1 способна1и2метретолько1способ.f(3)=1 f(3) = 1 f(3)=1 доскитолькона1и3метрахдоски только на 1 и 3 метрахдоскитолькона1и3метрах.f(4)=2 f(4) = 2 f(4)=2 доскимогутбытьна1,2и4,илина1и3доски могут быть на 1, 2 и 4, или на 1 и 3доскимогутбытьна1,2и4,илина1и3.f(5)=3 f(5) = 3 f(5)=3 возможныесочетания:1,2,3,5;1,2,4;1,3,4возможные сочетания: 1, 2, 3, 5; 1, 2, 4; 1, 3, 4возможныесочетания:1,2,3,5;1,2,4;1,3,4.f(6)=4 f(6) = 4 f(6)=4.f(7)=6 f(7) = 6 f(7)=6.f(8)=7 f(8) = 7 f(8)=7....Теперь, чтобы вычислить f(n) f(n) f(n), мы можем использовать следующие рекуррентные соотношения:
f(n)=f(n−1)+f(n−2)+f(n−7) f(n) = f(n - 1) + f(n - 2) + f(n - 7)
Инициализацияf(n)=f(n−1)+f(n−2)+f(n−7)
Определяем базовые значения:
f(1)=1 f(1) = 1 f(1)=1f(2)=1 f(2) = 1 f(2)=1f(3)=1 f(3) = 1 f(3)=1f(4)=2 f(4) = 2 f(4)=2f(5)=3 f(5) = 3 f(5)=3f(6)=4 f(6) = 4 f(6)=4f(7)=6 f(7) = 6 f(7)=6f(8)=7 f(8) = 7 f(8)=7РезультатТеперь вычислим f(20) f(20) f(20), используя динамическое программирование и заполнив массив f f f для всех значений до 20:
Программируем рекуррентную формулу от 1 до 20, сохраняя значения в массиве.Выведем значение f(20) f(20) f(20).В итоге, этот подход позволяет нам подсчитать количество способов построить забор длиной в 20 метров, с учетом всех условий, используя методы динамического программирования.