Архив форумов ЦИТФорума

[X-Ray]

Помогите решить задачку!

Найти количество покрытий прямоугольника 2*n(1<=n<=1000) фигурками в виде дощечок, каждая из которых представляеть собой 1*1, или 2*1, или уголок из трех квадратов 1*1.Фигурки должны заполнить прямоугольник без промежутков.

[DmitryShm]

Введи A(n) - число способов для доски вида 2.2.2..2.1 , B(n) - число способов для доски вида 2.2.2.2..2 . Ясно, что если доску перевернуть, то пустота над 1 всегда может быть сверху. На данное место всегда можно поставить 3 разные фигуры, понятно из условия. Для доски данной длины пробуем выразить кол-во способов через простые рекуррентности от A и B, понятно. Итак,
A(n) = B(n-1) + B(n-2), B(n) = A(n) + B(n-1) + A(n-1).

По-моему должно быть так.

Т.е. совет таков: если надо решить прям сейчас, то заводи 2 массива и за 1 проход решай. Если надо решить в замкнутой форме, т.е. получить решение в виде формулы B(n) = L(1,n,n^2), то используй производящие функции для получения формулы. Сейчас не хочу этого делать, т.к. мало времени.

Прочитай про динамическое программирование, чтобы научиться решать подобные задачки, ну и прочитай про производящие функции, чтобы получать формулы.
_________________
love IT

[X-Ray]

Я тут подумал! Напиши пожайлуста, если не трудно, где можно прочитать про динамическое программирование, чтобы научиться решать подобные задачки и про производящие функции, чтобы получать формулы.

[Гость]

Окуловские книжки подойдут: Окулов С. М. "Информатика в задачах", Пестов, Окулов "100 задач по информатике" -- это для школьников, а для более продвинутых Д. Кнут подойдет.