Ответ 1

Использование RPN (обратная польская нотация)

Для вставки RPN см. здесь.

Размер проблемы

Нам нужно построить список из четырех чисел, что подразумевает 3 оператора.
Эти числа и операторы будут выдвинуты или выполнены против стека.

Позволяет вызвать список выполнения {a1 a2 a3 a4 a5 a6 a7}.

{a1 a2} должны быть числами, так как в стеке нет никаких унаследованных операций.

{a7} должен быть оператором для завершения операции.

Для {a3, a4, a5, a6} у нас есть несколько опций, но всегда должно быть не менее двух чисел, которые должны быть в стеке, чтобы иметь возможность работать. Таким образом, возможные комбинации: (N = число, O = Оператор)

{N N O O}, {N O N O}, {O N O N}, {O N N O} и {N O O N}.

Комбинация {O O N N} запрещена, потому что стек пуст для второго O.

Итак, мы имеем:

      | {N N O O} |  
      | {N O N O} |  
{N N} | {O N O N} | {O}  
      | {O N N O} |  
      | {N O O N} |  

Теперь мы посчитаем возможные меры. Конечно, мы перечитываем, потому что коммутативный оператор (Плюс и Таймс) может сократить дерево перестановок пополам, но проблема достаточно мала, чтобы не беспокоиться об этом. (Мы также перечитываем в тех случаях, когда последовательность {O O}, но мы просто продолжаем..)

Мы должны выбрать 2 числа из четырех для первого сегмента, что 12 возможные меры.

Для среднего сегмента два оставшихся номера могут быть переписаны, что является фактором 2

Но у нас есть еще один фактор 5 для подсчета пяти альтернатив для среднего сегмента.

Для трех операторов, поскольку они могут повторяться, мы имеем коэффициент 4 ^ 3 = 64

Таким образом, размер проблемы является произведением чисел, выделенных полужирным шрифтом: 12 2 5 64 = 7680. Никакой оптимизации не требуется, мы можем идти грубой силой.

Остальная часть проблемы состоит в том, чтобы построить механизмы 7680 и оценщик RPN. Обе относительно простые задачи.

Я отправлю его... это еще черновик, но здесь слишком поздно! Завтра последует!

Изменить: Оценщик RPN

Вот код для рекурсивного оценщика RPN. Я решил сделать это на функциональном языке (Mathematica), чтобы упростить синтаксический анализ оператора

rpn[listipt_, stackipt_: {}] := 
  Module[{list=listipt,stack=stackipt}, (*recursive rpn evaluator*)

    If[list == {}, Return[stack[[1]]]];        (*end*)
    If[NumberQ[list[[1]]],                     (*if numeric*)
     [email protected][Rest[list], PrependTo[stack,list[[1]]]];  (*push nbr and recurse*)
    ,
     (stack[[2]]=list[[1]][stack[[2]], stack[[1]]];       (*if not, operate*)
      [email protected][Rest[list], Rest[stack]];);              (*and recurse*)
   ];
];

Примеры использования

rpn[{1, 1, 1, Plus, Plus}]
3

rpn[{2, 2, 2, Plus, Plus}]
6

rpn[{2, 3, 4, Plus, Times}]  (* (4+3)*7 *)
14

rpn[{2, 3, 4, Plus, Divide}]  (* (2+3)/4 *)
2/7  

чуть позже я отправлю генератор кортежей, покажу, что они 7680 и некоторые забавные результаты о распределении возможных результатов операций (фактически для набора {1,2,3,4} вы можете получите только 230 результатов!).

Изменить: построение кортежей

Сначала мы явно построим возможности для среднего сегмента

t1 = {{n3, n4, o1, o2}, 
      {n3, o1, n4, o2}, 
      {o1, n3, o2, n4}, 
      {o1, n3, n4, o2}, 
      {n3, o1, o2, n4}};

Теперь мы добавим два варианта для {n1, n2} и последнего оператора

t2 = Join[Map[Join[{n1, n2}, #, {o3}] &, t1], 
          Map[Join[{n2, n1}, #, {o3}] &, t1]] ( bahh ... don't mind the code*)

Результат в наших 10 различных конфигурациях

Теперь мы должны заполнить все эти конфигурации всеми возможными перестановками чисел и операторов.

Сначала построим все перестановки чисел в качестве правил назначения для наших кортежей

 repListNumbers = (*construct all number permutations*)
    Table[{n1 -> #[[1]], n2 -> #[[2]], n3 -> #[[3]], n4 -> #[[4]]} &[i], 
         {i, Permutations[{1, 2, 3, 4}]}];

Эти маленькие зверь имеют форму

  {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}

И мы можем использовать их для замены vallues в наших кортежах. Например:

  {n1,n2,n3,o1,o2,n4,o3} /. {n1 -> 1, n2 -> 2, n3 -> 3, n4 -> 4}

Результаты в

  {1,2,3,o1,o2,4,o3}

Конечно, мы могли бы построить правила замены как функцию, чтобы иметь возможность изменять число, заданное по желанию. Теперь мы делаем что-то подобное с операторами

repListOps =      (*Construct all possible 3 element tuples*)
  Table[{o1 -> #[[1]], o2 -> #[[2]], o3 -> #[[3]]} &[i], 
      {i, Tuples[{Plus, Times, Divide, Subtract}, 3]}];    

Итак, мы получаем набор таких вещей, как

 {o1->Plus, o2->Plus, o3->Divide}

Теперь мы объединяем наши кортежи и все наши правила замены в одном большом списке:

t3 = Flatten[t2 /. repListNumbers /. repListOps, 2];

Это приводит к 15360 различным вычислениям. Но мы знаем, что их пересчитаны в два раза, поэтому теперь мы бросаем повторяющиеся элементы:

t3 =Union[t3]

И это даст нам наши ожидаемые элементы 7680.

Есть еще некоторый перерасчет, потому что {2,3, Times} = {3,2, Times} = 6, но это нормально для наших текущих purpouses.

Оценка результатов

Теперь у нас есть наш оценщик RPN и все эти кортежи, и мы хотим знать, возможен ли определенный конечный результат.

Мы просто должны спросить, содержится ли это число в наборе результатов:

In[252]:= MemberQ[rpn /@ t3, 24]
Out[252]= True

In[253]:= MemberQ[rpn /@ t3, 38]
Out[253]= False

Фактически оценки для набора результатов:

In[254]:= Max[rpn /@ t3]
Out[254]= Max[36, ComplexInfinity]

In[255]:= Min[rpn /@ t3]
Out[255]= Min[-23, ComplexInfinity]

Результаты бесконечности связаны с тем, что меня не интересовали деления на ноль, так что они там, только внутри набора. Цифровой интервал [-23,36].

Если вы хотите знать, сколько результатов равно 24, просто посчитайте их

      In[259]:= [email protected][t3, rpn[#] == 24 &]
      Out[259]= 484

Конечно, многие из них являются тривиальными перестановками из-за коммутативных свойств "Плюс" и "Таймс", но не все:

   {1, 2, Plus, 3, Plus, 4, Times}      -> ((1+2)+3)*4  = 24
   {2, 1, 4, 3, Times, Divide, Divide}  ->  2/(1/(4*3)) = 24

Нет последовательности с использованием "Вычитания", которая дает 24!

    In[260]:= MemberQ[[email protected][t3, rpn[#] == 24 &], Subtract]
    Out[260]= False

Результаты Спектр образца