Question

Перед уроком по алгоритмам студенты рисуют на доске котиков. Условно доска — поле размером 2х5 из равных

квадратов. Преподаватель не стирает котиков, но место для рассказываемого материала оставить надо. Поэтому

студенты рисуют от 1 до 3 котиков, каждый из которых занимает целое число клеток: хотя бы одну, но не более

двух, смежных по стороне. Причём в общем все котики не занимают более трёх клеток. Различные котики могут

находиться в смежных (и по стороне, и по углу) клетках.

Сколькими способами студенты могут нарисовать котиков, где различными способами считаются те, в которых

двух одинаковых по размеру котиков меняют местами?

Answer 1

Ответ:

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.