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

Все удачные наборы команд должны включать остановку на отметке 12 футов.На отметку 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).Напимер, на отметку 4 фута робот может попасть с отметок 3, 2 или 1 фут, следовательно, количество способов попасть на отметку 4 определяется как K(3)+K(2)+K(1).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 = 274K(11) = K(10)+K(9)+K(8) = 274+149+81 = 504K(12) = K(11)+K(10)+K(9) = 504+274+149 = 927Так как вторая часть пути робота также имеет длину 12, то общее количество удачных наборов команд = 927*927 = 859 329