Задача по информатике Вовочке надо построить забор из досок длиной в 14 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать 1 или 4 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.

15 Сен 2024 в 19:40
655 +1
0
Ответы
1

Для решения этой задачи можно воспользоваться динамическим программированием.

Пусть dpnnn - количество способов построить забор длиной n метров.

Из условия задачи следует, что dp111 = dp141414 = 1, так как на первом и последнем метрах должна быть прибита доска.

Далее, можно заметить, что если на n-м метре доска прибита, то на n-1 и n-2 метрах доски быть не может, так как нельзя пропускать более 4 метров. Иначе, если на n-м метре доска не прибита, то на n-1 метре доска должна быть прибита.

Таким образом, формула для dpnnn будет выглядеть следующим образом:
dpnnn = dpn−1n-1n1 + dpn−3n-3n3 + dpn−4n-4n4

Используя эту формулу, заполним массив dp по очереди, начиная с dp222 и заканчивая dp141414.

Python код для решения задачи:

dp = 000 * 15
dp111 = dp141414 = 1
for i in range2,152, 152,15:
dpiii = dpi−1i-1i1 + dpi−3i-3i3 + dpi−4i-4i4
printdp[14]dp[14]dp[14]

Ответ: Существует 710 способов построить забор.

15 Сен 2024 в 19:40
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир