Конечная клетка Кузнечика
Конечная клетка Кузнечика — это клетка, в которой исполнитель должен оказаться после выполнения всех условий задачи. Её находят по формулировке условия и используют как последнюю точку при подсчёте маршрутов.
Кузнечик обычно перемещается только вправо: например, на 1, 2 или 3 клетки за один шаг Кузнечика. Если начальная клетка имеет номер \(1\), а попасть нужно в клетку \(N\), то \(N\) — конечная клетка. Все допустимые маршруты должны заканчиваться именно в ней, а не просто проходить через неё.
Как используется в задаче
Сначала определяют, из какой клетки начинается движение и в какую клетку оно должно завершиться. Затем рассматривают маршрут Кузнечика и подсчитывают способы попасть в каждую клетку. Если \(F(k)\) — число маршрутов из начальной клетки в клетку \(k\), то ответом будет значение \(F(N)\), где \(N\) — номер конечной клетки.
Кузнечик начинает в клетке 1 и может прыгать на 1 или 2 клетки. По условию он должен попасть в клетку 5. Значит, конечная клетка — 5, а учитываются только маршруты, заканчивающиеся в 5: \(1\to2\to3\to4\to5\), \(1\to2\to3\to5\), \(1\to2\to4\to5\) и другие допустимые варианты.
Конечная клетка — это цель движения, а не последний промежуточный прыжок. Запрещённая клетка может находиться до конечной клетки: через неё нельзя проходить, но сама конечная клетка обычно разрешена, если условие не говорит обратное.
Кузнечик стартует в клетке 3 и должен прийти в клетку 10. Какая клетка является конечной?
Главное
- Конечная клетка — последняя клетка маршрута, в которую должен попасть Кузнечик.
- Если \(F(k)\) обозначает число маршрутов до клетки \(k\), ответ обычно равен \(F(N)\), где \(N\) — номер конечной клетки.
- Конечную клетку не следует путать с начальной, промежуточной или запрещённой клеткой.