Перед уроком по алгоритмам студенты рисуют на доске котиков. Условно доска -поле размером 2х3 из равных
квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому
студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более
двух, смежных по стороне. Причём в общем все котики не занимают более трёх клеток. Различные котики могут
находиться в смежных (и по стороне, и по углу) клетках.
Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых
двух одинаковых по размеру котиков меняют местами?
(В ответ запиши только число без пробелов.)
квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому
студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более
двух, смежных по стороне. Причём в общем все котики не занимают более трёх клеток. Различные котики могут
находиться в смежных (и по стороне, и по углу) клетках.
Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых
двух одинаковых по размеру котиков меняют местами?
(В ответ запиши только число без пробелов.)
More Questions From This User See All
Answers & Comments
Ответ:
4
Пошаговое объяснение:
Для решения данной задачи можно воспользоваться методом динамического программирования.
Обозначим F(n) - количество способов нарисовать котиков на поле размером n.
Так как каждый котик занимает от 1 до 2 смежных клеток, то есть два возможных способа размещения котика: горизонтальное и вертикальное.
Рассмотрим случай, когда на поле размером n нарисовано k котиков. Чтобы добавить еще одного котика, мы должны разместить его на одной из двух возможных позиций: горизонтальной или вертикальной.
Если разместить котика горизонтально, то размер поля станет n - 2. Поэтому количество способов нарисовать котиков на поле размером n - 2 и с k - 1 котиками будет равно F(n - 2) * F(k - 1).
Если разместить котика вертикально, то размер поля станет n - 1. Поэтому количество способов нарисовать котиков на поле размером n - 1 и с k котиками будет равно F(n - 1) * F(k).
Таким образом, количество способов нарисовать котиков на поле размером n и с k котиками будет равно F(n - 2) * F(k - 1) + F(n - 1) * F(k).
Используя данный рекуррентный соотношение, мы можем построить таблицу значений F(n) для всех n от 0 до 3.
F(0) = 1 (пустое поле)
F(1) = 1 (1 клетка)
F(2) = 2 (2 горизонтальные клетки, 1 вертикальная клетка)
F(3) = 4 (2 горизонтальные клетки и 1 вертикальная клетка; 1 горизонтальная клетка и 2 вертикальные клетки; 1 горизонтальная клетка и 1 вертикальная клетка)
Таким образом, студенты могут нарисовать котиков на поле размером 2x3 всего 4 способами.