использовать Чертежник
алг
нач
сместиться в точку (1, 2)
опустить перо
сместиться в точку (2, 2)
сместиться в точку (2, 0)
сместиться в точку (1, 0)
сместиться в точку (1, 2)
поднять перо
сместиться в точку (3, 2)
опустить перо
сместиться в точку (4, 2)
сместиться в точку (3, 1)
сместиться в точку (3, 0)
поднять перо
сместиться в точку (6, 1)
опустить перо
сместиться в точку (7, 2)
сместиться в точку (7, 0)
поднять перо
сместиться в точку (8, 2)
опустить перо
сместиться в точку (9, 2)
сместиться в точку (9, 1)
сместиться в точку (8, 0)
сместиться в точку (9, 0)
поднять перо
сместиться в точку (11, 2)
опустить перо
сместиться на вектор (1,0)
сместиться на вектор (0,-1)
сместиться на вектор (-1,-1)
сместиться на вектор (1,0)
поднять перо
сместиться в точку (13, 2)
опустить перо
сместиться на вектор (1,0)
сместиться на вектор (0,-2)
сместиться на вектор (-1,0)
сместиться на вектор (0,2)
поднять перо
сместиться в точку (15, 2)
опустить перо
сместиться на вектор (1,0)
сместиться на вектор (0,-2)
сместиться на вектор (-1,0)
сместиться на вектор (0,2)
поднять перо
сместиться в точку (17, 2)
опустить перо
сместиться на вектор (1,0)
сместиться на вектор (-1,-1)
сместиться на вектор (1,0)
сместиться на вектор (-1,-1)
поднять перо
сместиться в точку (0, 0)
кон
Объяснение:
На отметку 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 = 7
K(5) = K(4)+K(3)+K(2) = 7+4+2 = 13
K(6) = K(5)+K(4)+K(3) = 13+7+4 = 24
K(7) = K(6)+K(5)+K(4) = 24+13+7 = 44
K(8) = K(7)+K(6)+K(5) = 44+24+13 = 81
K(9) = K(8)+K(7)+K(6) = 81+44+24 = 149
K(10) = K(9)+K(8)+K(7) = 149+81+44 = 274
Так как вторая часть пути робота также имеет длину 10, то общее количество удачных наборов команд = 274*274= 75076