Ответ 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
Результаты Спектр образца
