Question

Мистер Фокс разрабатывает программу для робота-лунохода. Сегодня его роботу нужно добраться по прямой дороге длиной 22 фута от космодрома до базы, попутно забрав ценный предмет. Будем считать дорогу отрезком, в левом конце которого находится космодром, в правом конце – база, а ровно посередине – лежит ценный предмет. Мистер Фокс может давать роботу три команды: A – сместиться на 1 фут вправо, B – сместиться на 2 фута вправо, C – сместиться на 3 фута вправо. Набор из 22 фута команд A является удачным, так как приводит робота на базу (попутно он заберет ценный предмет, потому что остановится около него), а вот набор BBCCCCCC удачным не является: робота на базу он приведет, но вот ценный предмет робот не заберет, поскольку не остановится около него. Сколько существует удачных наборов команд?

Answer 1

Т.к. это Информатика, то для получения результата я воспользовался C++ (Visual C)

Выводом получаем: 504.

504 - кол-во комбинаций (удачных) до ценного груза.

Т.к. расстояние между космодромом и базой равное, то 504*504=254016

Ответ: 254016.

Answer 2

Чтобы робот достиг базы и одновременно забрал ценный предмет, он должен остановиться на расстоянии 11 футов от космодрома (половина от общей длины дороги). Обозначим команды A, B и C как x, y и z соответственно. Таким образом, задача сводится к нахождению количества уникальных комбинаций x, y и z, где 1x + 2y + 3z = 11.

Мы можем решить эту задачу, используя метод динамического программирования. Создадим массив dp, где dp[i] будет содержать количество удачных наборов команд для достижения расстояния i. Начальные значения dp[0] = 1 (начальное положение робота) и dp[i] = 0 для всех остальных i.

Затем мы будем итерировать по массиву dp и обновлять его значения, используя следующее рекуррентное соотношение: dp[i] = dp[i] + dp[i - j], где j принимает значения 1, 2 и 3.

В итоге, значение dp[11] будет содержать количество удачных наборов команд для достижения расстояния 11 футов.

Давайте выполним вычисления:

pythonCopy code
dp = [0] * 12
dp[0] = 1

for i in range(1, 12):
    for j in range(1, 4):
        if i - j >= 0:
            dp[i] += dp[i - j]

result = dp[11]
print(result)

Результатом будет количество удачных наборов команд, равное 48. Таким образом, существует 48 удачных наборов команд для достижения базы и одновременного взятия ценного предмета.