Использование RPN (обратная польская запись)
Для ознакомления с RPN см. здесь .
Размер задачи
Мы должны составить список из четырех чисел, что подразумевает 3 оператора.
Эти числа и операторы будут выталкиваться или выполняться со стеком.
Позволяет вызвать список выполнения {a1 a2 a3 a4 a5 a6 a7}.
{a1 a2} должны быть числами, поскольку в стеке нет унарных операций.
{a7} должен быть оператором, чтобы завершить операцию.
Для {a3, a4, a5, a6} у нас есть несколько вариантов, но всегда должно быть хотя бы два числа в стеке, чтобы иметь возможностьработать.Таким образом, возможные комбинации: (N = число, O = оператор)
{NNOO}, {NONO}, {ONON}, {ONNO} и {NOON}.
Комбинация {OONN} запрещена, поскольку стек для второго O пуст.
Итак, мы имеем:
| {N N O O} |
| {N O N O} |
{N N} | {O N O N} | {O}
| {O N N O} |
| {N O O N} |
Теперь мыбудет рассчитывать возможные меры.Конечно, мы перестаем считать, потому что коммутативный оператор (Plus и Times) может разрезать дерево перестановок пополам, но проблема достаточно мала, чтобы не беспокоиться об этом.(Мы также переоцениваем значения в тех случаях, когда последовательность равна {OO}. Но мы просто продолжаем ..)
Мы должны выбрать 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*)
Return@rpn[Rest[list], PrependTo[stack,list[[1]]]]; (*push nbr and recurse*)
,
(stack[[2]]=list[[1]][stack[[2]], stack[[1]]]; (*if not, operate*)
Return@rpn[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}
И мы можем использовать их для замены valсифилис в наших кортежах.Например:
{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, но это нормально для наших нынешних целей.
Оценка результатов
Теперь у нас есть наш оценщик 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]:= Length@Select[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[Flatten@Select[t3, rpn[#] == 24 &], Subtract]
Out[260]= False
Результаты Спектр образца
