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

может не 274*274, а 274+274?

Я так и не додумался, как рассчитать, и просто вручную перебрал подходящие варианты (для половины пути, до 10 футов). Получилось так же, 274 варианта. Дальше аналогично планировал перемножить.

Ziorar, получается если прямая дорога будет 22 длиной фунтов, то получится удачные наборы команд на отметке 11? Я правильно понял?

????

Ну да, в той задаче, где 22 фута путь, тоже было сказано, что ровно посередине лежит ценный предмет (т.е. на 11 футах, и около него так же нужно сделать остановку).

Все удачные наборы команд должны включать остановку на отметке 10 футов.На отметку 1 фут робот может попасть с помощью одной команды A;на отметку 2 фута - с помощью команд AA и B (всего 2 набора команд);на отметку 3 фута - с помощью команд AAA, AB, BA и C (4 набора).Так как за одну команду робот может переместиться на 1, 2 или 3 фута, то для подсчета количества наборов команд, позволяющих роботу попасть на отметки N > 3, можно использовать формулу K(N) = K(N-1)+K(N-2)+K(N-3).K(4) = K(3)+K(2)+K(1) = 4+2+1 = 7K(5) = K(4)+K(3)+K(2) = 7+4+2 = 13K(6) = K(5)+K(4)+K(3) = 13+7+4 = 24K(7) = K(6)+K(5)+K(4) = 24+13+7 = 44K(8) = K(7)+K(6)+K(5) = 44+24+13 = 81K(9) = K(8)+K(7)+K(6) = 81+44+24 = 149K(10) = K(9)+K(8)+K(7) = 149+81+44 = 274Так как вторая часть пути робота также имеет длину 10, то общее количество удачных наборов команд = 274*274 = 75076