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

а откуда взялась такая формула?

вот именно!

Так как за одну команду робот может переместиться на 1, 2 или 3 фута, то ... Другими словами: на отметку 4 фута робот может попасть с отметок 3, 2 или 1 фут, следовательно, количество способов попасть на отметку 4 определяется как K(3)+K(2)+K(1).

Я приведу программное решение, так как это все-таки информатика. Аналитическое решение ищите по ссылке в комментарияхКод на Ruby 2def f0(number, log) #  v = 1  n = number + v  log = "#{log}A"  return [n, log]enddef f1(number, log) #  v = 2  n = number + v  log = "#{log}B"  return [n, log]enddef f2(number, log) #  v = 3  n = number + v  log = "#{log}C"  return [n, log]enddef countWays(start_num, end_num, op_number, max_steps = 0)  ways = {}  ways.store(start_num.to_s, start_num)  max_steps = max_steps == 0 ? (start_num - end_num).abs : max_steps  count = 0  for steps in 1..max_steps      new_ways = {}      ways.each_pair{|log, num|          for k in 0..op_number-1              num1, log1 = f0(num, log) if k == 0              num1, log1 = f1(num, log) if k == 1              num1, log1 = f2(num, log) if k == 2              if num1 == end_num then                  log1 += " = " + end_num.to_s                  count += 1                  # puts log1              elsif num1.between?(start_num, end_num)                  new_ways.store(log1, num1)              end          end      }      ways = new_ways  end  return countendp countWays(0, 11, 3) # с 0 до 11, 3 разных командыВывод 504Поскольку длина путей до ценного объекта и от объекта до базы - равны, то всего вариантов 504*504 = 254016

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