Ламинат или Количество способов замостить прямоугольник MN прямоугольниками M1 и 1*M

@Kuzya31 · Регистрация: 25.10.2019

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

Ламинат
Требуется замостить пол комнаты шириной N и длиной M с помощью N полос ламината размером 1xM. Самый простой способ укладки - N полос, одну возле одной. Однако, в разработанной игре можно укладывать полосы ламината как вдоль длины комнаты, так и вдоль ширины. При этом пилить или ломать полосы ламината нельзя. Также нельзя укладывать одну полосу поверх другой. Все полосы должны лежать на полу, не оставляя непокрытых мест. При таком подходе можно придумать много способов укладки ламината, например, для комнаты шириной 3 и длиной 2 существует 3 способа укладки. Для заданных M и N требуется определить количество допустимых способов укладки.
Формат входных данных
Входные данные состоят из одной строки, которая содержит два натуральных числа M и N (1 ≤ N ≤ 40, 2 ≤ M ≤ 10).
Формат результата
В качестве результата нужно записать одно число – количество допустимых способов укладки ламината.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
 
using namespace std;
int main()
{
 
    int n,m,k,res=0;
    cin>>m>>n;
    if(n<m)cout<<1;
    else {
    double K =n/m;
    k = (int) K;
    res= 1+k;
    for(int a = 1; a<=k; a++)
    {
        res+=(n-a*m)*a;
    }
cout<<res;
return 0;
}
}

проходит только 3 теста.
Пожалуйста, помогите решить и разобраться в алгоритме)

@nalbe666 · 16.02.2020, 04:14

...

@_Ivana · 16.02.2020, 06:19

C++
1
2
3
int f (int n, int m) { int r=1; for (int j=0; m+j<=n; j++) r += f(n-m-j, m); return r; }
 
int main() { int n, m; std::cin >> m >> n; std::cout << f(n, m); }

PS мемоизацию добавить по вкусу. Но при данных диапазонах аргументов и без нее норм.

@Kuzia domovenok · 16.02.2020, 10:22

_Ivana, специально ли так вырвиглазно написано, чтоб автор ничего не понял?

@_Ivana · 16.02.2020, 14:23

Каждый судит о мотивах других, исходя из своих.

Сообщение от ValeryS

у_Ivana своя логика, каждая строчка свой функциональный блок, тем более что он не только на Си пишет

ЗЫ переформатировать кота сможет любой.

@Kuzia domovenok · 17.02.2020, 13:56

_Ivana, да как бы ты ни любил "функциональные блоки"...
писать обфусцированные функции с именем f и переменной r, без комментариев и пояснений - это говнокод на любом языке/в любой парадигме программирования.

@_Ivana · 17.02.2020, 21:33

Конечно

Лучше писать ноющие посты на форумах про чужой говнокод, когда сам ниасилил задачу

ЗЫ для справки, давным давно, много лет назад, у нас с вами состоялся нелицеприятный диалог, вследствие которого я сформировал о вас определенное мнение. С тех пор оно только укрепилось

Поэтому вы можете продолжать задавать мне вопросы, высказывать свое мнение по поводу мотивов моих действий и качества моего кода, но, думаю, вы догадываетесь, как я к этому отношусь

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	16.02.2020, 04:14
	... 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	16.02.2020, 10:22
	_Ivana, специально ли так вырвиглазно написано, чтоб автор ничего не понял? 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	17.02.2020, 13:56
	_Ivana, да как бы ты ни любил "функциональные блоки"... писать обфусцированные функции с именем f и переменной r, без комментариев и пояснений - это говнокод на любом языке/в любой парадигме программирования. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	17.02.2020, 21:33
	Конечно Лучше писать ноющие посты на форумах про чужой говнокод, когда сам ниасилил задачу ЗЫ для справки, давным давно, много лет назад, у нас с вами состоялся нелицеприятный диалог, вследствие которого я сформировал о вас определенное мнение. С тех пор оно только укрепилось Поэтому вы можете продолжать задавать мне вопросы, высказывать свое мнение по поводу мотивов моих действий и качества моего кода, но, думаю, вы догадываетесь, как я к этому отношусь 0

Ламинат или Количество способов замостить прямоугольник M*N прямоугольниками M*1 и 1*M

Решение

Ламинат или Количество способов замостить прямоугольник MN прямоугольниками M1 и 1*M