Перед уроком по алгоритмам студенты рисуют на доске котиков. Условно доска — поле размером 2х5 из равных
квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому
студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более
двух, смежных по стороне. Причём в общем все котики не занимают более трёх клеток. Различные котики могут
находиться в смежных (и по стороне, и по углу) клетках.
Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых
двух одинаковых по размеру котиков меняют местами?
Ответы
Ответ:
13
Объяснение:
Для решения этой задачи можно использовать метод динамического программирования. Предлагаю рассмотреть следующую таблицу:
| Количество клеток | Количество способов |
|--------------------|---------------------|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 7 |
| 5 | 13 |
Заполняя таблицу, мы можем заметить, что количество способов рисования котиков на доске размером n клеток зависит от количества способов рисования котиков на доске размером n-1 клеток и n-2 клеток.
Таким образом, мы можем записать рекуррентную формулу: f(n) = f(n-1) + f(n-2), где f(n) - количество способов рисования котиков на доске размером n клеток.
Применяя эту формулу, мы можем вычислить количество способов рисования котиков на доске размером 5 клеток, которое равно 13.