Перед уроком по алгоритмам студенты рисуют на доске котиков. Условно доска -поле размером 2х4 из равных
квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому
студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более
двух, смежных по стороне. Причем в общем все котики не занимают более трех клеток. Различные котики могут
находиться в смежных (и по стороне, и по углу) клетках.
Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых
двух одинаковых по размеру котиков меняют местами?
(В ответ запиши только число без пробелов.)
квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому
студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более
двух, смежных по стороне. Причем в общем все котики не занимают более трех клеток. Различные котики могут
находиться в смежных (и по стороне, и по углу) клетках.
Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых
двух одинаковых по размеру котиков меняют местами?
(В ответ запиши только число без пробелов.)
More Questions From This User See All
Answers & Comments
Ответ:
7
Пошаговое объяснение:
Для решения данной задачи можно использовать метод динамического программирования. Пусть dp[i] будет количество способов нарисовать котиков на поле размером i. Тогда можно выразить dp[i] через предыдущие значения dp[j], где j < i.
Имеется несколько базовых случаев:
- dp[0] = 1, так как на пустом поле нет возможности нарисовать котиков.
- dp[1] = 1, так как на поле размером 1x1 есть только один возможный вариант нарисовать котика.
- dp[2] = 2, так как на поле размером 2x1 можно нарисовать одного котика или двух котиков, занимающих по клетке.
Далее, для dp[i] с i > 2, можно выразить через предыдущие значения следующим образом:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
Таким образом, чтобы найти количество способов нарисовать котиков на поле размером 2x4, нужно вычислить dp[4].
Вычисляя значения dp[i] для каждого i от 0 до 4, получаем:
dp[0] = 1
dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = 7
Ответ: 7