Подсчитать количество способов замощения полосы 2 × n с помощью плиток

@Gerasick · Регистрация: 15.11.2023

Студворк — интернет-сервис помощи студентам

Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу размером 2 × n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать. Вам необходимо написать программу для подсчета количества способов замощения полосы 2 × n с помощью плиток указанного вида.

Примеры:
Ввод: 2, Вывод 7

Ввод: 3, Вывод 22

(Прошу писать программу как можно более простой и понятной, спасибо.)

@AntDevel · 19.11.2023, 17:04

параметром передаётся n ?

@Gerasick · 19.11.2023, 17:38 **[ТС]**

вводится n

@igorrr37 · 19.11.2023, 18:42

мей би так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n = 3
m = 2
 
vCan = [[0 for _ in range(m+1)] for _ in range(n+1)]
vCan[0][0] = 1
vCan[0][1] = 1
vCan[0][2] = 1
vCan[1][0] = 1
vCan[1][1] = 0
vCan[1][2] = 1
vCan[2][0] = 1
vCan[2][1] = 1
vCan[2][2] = 0
 
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
dp[0][0] = 1
 
for i in range(1, n+1):
    for nMask in range(m+1):
        for pMask in range(m+1):
            dp[i][nMask] += dp[i-1][pMask] * vCan[pMask][nMask] * (2 if pMask == 0 and nMask == 0 else 1)
            if i >= 2 and pMask == 0 and nMask == 0:
                dp[i][nMask] += dp[i-2][pMask]
 
print(dp[-1][0])

@eaa · 19.11.2023, 18:56

Python
1
2
3
4
a, b, c = 1, 2, 7
for _ in range(int(input())):
    a, b, c = b, c, 3 * c + b - a
print(a)

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@Gerasick 11 / 10 / 1 Регистрация: 15.11.2023 Сообщений: 55

	Подсчитать количество способов замощения полосы 2 × n с помощью плиток 19.11.2023, 15:50. Показов 1373. Ответов 4 Метки нет (Все метки) Имеются прямоугольные плитки двух типов — одноклеточные квадраты размером 1 × 1 и двухклеточные прямоугольники размером 1 × 2. С помощью этих плиток необходимо замостить полосу размером 2 × n, при этом плитки не должны накладываться друг на друга и каждая клетка полосы должна быть покрыта ровно одной плиткой. Плитки разрешается поворачивать. Вам необходимо написать программу для подсчета количества способов замощения полосы 2 × n с помощью плиток указанного вида. Примеры: Ввод: 2, Вывод 7 Ввод: 3, Вывод 22 (Прошу писать программу как можно более простой и понятной, спасибо.) 0

@AntDevel 8 / 8 / 0 Регистрация: 17.09.2023 Сообщений: 58
	19.11.2023, 17:04
	параметром передаётся n ? 0

@Gerasick 11 / 10 / 1 Регистрация: 15.11.2023 Сообщений: 55
	19.11.2023, 17:38 [ТС]
	вводится n 0