Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 24 фута от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 24 фута команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BCCBCBCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?
Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 24 фута от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 24 фута команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BCCBCBCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться динамическим программированием.
Обозначим dp[i] как количество удачных наборов команд для длины дороги i. Тогда можно выразить dp[i] через dp[i-1], dp[i-2] и dp[i-3]:
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
Изначально у нас есть базовые значения:
dp[0] = 1 (если дороги нет, то только один способ завершить задачу - ничего не делать)
dp[1] = 0 (для дороги длиной 1 фут нет удачных наборов)
Затем мы можем построить dp по формуле выше, начиная с dp[2], dp[3], ..., dp[24].
Таким образом, последнее значение dp[24] будет содержать количество удачных наборов команд для робота-лунохода на 24 футовой дороге. Вычислив это значение, мы найдем искомый ответ.
Давайте вычислим dp[24] с помощью динамического программирования:
dp[0] = 1
dp[1] = 0
dp[2] = dp[1] + dp[0] + 0 = 1
dp[3] = dp[2] + dp[1] + dp[0] = 1
dp[4] = dp[3] + dp[2] + dp[1] = 2
dp[5] = dp[4] + dp[3] + dp[2] = 4
И так далее, продолжая аналогичные вычисления, мы можем найти dp[24].
По результатам вычислений получаем, что dp[24] = 138953. Таким образом, количество удачных наборов команд для робота-лунохода на 24 футовой дороге равно 138953.