Question

СРОЧНО! На очень большом листе клетчатой бумаги нарисовали систему координат. В точке (0; 0) маленький робот. Он может выполнять команды RIGHT, LEFT, UP, DOWN, смещаясь на единичный отрезок в соответствующем направлении. Вася пишет программу для робота, состоящую ровно из 12 команд и приводящую его в точку с координатами (7; 3). Ему стало интересно: а сколько всего существует таких программ? Помогите ему ответить на этот вопрос. В качестве ответа укажите одно натуральное число — количество таких команд. Комментарий. Если робот находится в начале координат и выполнил команду RIGHT, он окажется в точке (1; 0). Если после этого он выполнит команду LEFT, то вернется обратно в точку (0; 0). Если теперь он выполнит команду UP, то окажется в точке (0; 1), а если затем выполнит команду DOWN, то опять вернется в точку (0; 0). Программа робота – это набор команд. Программы, отличающиеся перестановкой команд, считаются различными. Например, есть 9 различных программ, состоящие ровно из 3 команд, приводящие робота из точки (0; 0) в точку (1; 0): RIGHT LEFT RIGHT; UP DOWN RIGHT; DOWN UP RIGHT; UP RIGHT DOWN; DOWN RIGHT UP; RIGHT UP DOWN; RIGHT DOWN UP; RIGHT RIGHT LEFT.

Answer 1

Ответ: 5940

var steps := 12; // За кол-во ходов
var Xend  := 7; // В точку с координатой X
var Yend  := 3; // ... и Y

var vars := 0; procedure Find(step, X, Y : Integer);

begin  
    if step = 0 then    
        vars += (X = Xend) and (Y = Yend) ? 1 : 0
    else    
        begin      
             Find(step - 1, X + 1, Y    );      
             Find(step - 1, X - 1, Y    );      
             Find(step - 1, X    , Y + 1);      
             Find(step - 1, X    , Y - 1);    
        end;
end; 
begin  
     Find(steps, 0, 0);  
     Print(vars);
end.

Answer 2

Для решения данной задачи можно использовать комбинаторику и рассмотреть все возможные комбинации команд.

Из условия задачи известно, что робот должен сделать 7 шагов вправо (RIGHT) и 3 шага вверх (UP), чтобы достичь точки (7; 3).

Мы можем представить команды RIGHT как букву R и команды UP как букву U. Теперь нам нужно найти все возможные перестановки букв R и U в строке длиной 12 символов.

Для этого мы можем использовать формулу сочетаний с повторениями. Общая формула для количества сочетаний с повторениями из n элементов, где каждый элемент может повторяться k раз, выглядит следующим образом:

C(n + k - 1, k)

В нашем случае n = 2 (количество различных команд: R и U), а k = 12 (длина строки команд). Подставляя значения в формулу, получаем:

C(2 + 12 - 1, 12) = C(13, 12) = 13

Таким образом, существует 13 различных программ, состоящих ровно из 12 команд, которые приводят робота в точку (7; 3).