Recombine Number to Equal Math Formula

Question

Я думал о проблеме математики/алгоритма и был бы благодарен за ваш вклад в решение проблемы!

Если у меня есть номер (например, 479), я бы хотел перекомпилировать его цифры или их комбинацию с математической формулой, соответствующей исходному номеру. Все цифры должны быть использованы в их исходном порядке, но могут быть объединены для чисел (и, следовательно, 479 допускает 4, 7, 9, 47, 79), но каждая цифра может быть использован только раз, так вы не можете иметь что-то вроде 4x47x9, так как теперь номер 4 использовался дважды.

Теперь пример, чтобы продемонстрировать, как я думаю об этом. Пример математически неверен, потому что я не мог придумать хороший пример, который действительно работает, но он демонстрирует входные и ожидаемые результаты.

Пример ввода: 29485235

Результат: 2x9+48/523^5

Как я сказал, мой пример делает не добавить вверх (2x9 + 48/523^5 не приводит к 29485235), но я задавался если есть алгоритм, который фактически позволил бы мне найти такую ​​формулу, состоящую из цифр исходного номера в их первоначальном порядке, который при вычислении даст исходное число.

О типе используемой математики, я бы сказал, скобки() и Add/Sub/Mul/Div/Pow/Sqrt.

Любые идеи о том, как это сделать? Моя мысль заключалась в том, чтобы просто грубо заставлять ее, разделяя число на случайное и делая расчеты, надеясь на результат. Должен быть лучший способ, хотя?

Edit: Если это проще в неоригинальной порядке, или у вас есть идея, чтобы решить эту проблему, игнорируя при этом некоторые из «условий», описанных выше, он все равно поможет чрезвычайно, чтобы понять, как идти о решении таких проблема.

Answer 1

Номера, как я помню, чрезвычайно редки, если они сохранились. Некоторые цифры могут быть выражены цифрами их компонентов в разных заказах, например, 25 (5²).

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

EDIT: Частичное решение.

Частичным решением, решающим в некоторых случаях, является разложение числа на его первичные факторы. Если его простые множители одинаковы, а показатель и коэффициент присутствуют в цифрах числа (например, 25), у вас есть конкретное решение.

Большинство номеров, которые делают, попадают в такие виды узоров, которые будут делать это либо с умножением, либо с помощью pow() в качестве основной движущей силы; добавление просто не увеличивает его достаточно.

Answer 2

Недостаточно построить нейронную сеть, которая воспроизводит Кэрол Воордерман. Я не вижу ничего, кроме работы с грубой силой. Люди очень умны, видя шаблоны в таких проблемах, как это, но кодирование такого прозрения очень сложно.

Answer 3

Для чисел примерно до 6 цифр или около того, я бы сказал, что перебор его в соответствии со следующей схемой:

1) Разделите начальное значение в список (массив, что угодно, в зависимости от языка) чисел. Первоначально это цифры.

2) Для каждой пары чисел объедините их вместе с использованием одного из операторов. Если результатом является целевой номер, то верните успех (и распечатайте все операции, выполняемые при выходе). В противном случае, если это целое число, запишите новый, меньший список, состоящий из числа, которое вы только что подсчитали, и числа, которые вы не использовали. Или вы можете разрешить нецелые промежуточные результаты, что сделает пространство поиска несколько больше. Бинарные операции:

• Добавить
• вычитать
• размножаются
• делят
• мощность
• конкатенации (который может быть использован только на номера, которые являются либо оригинальные цифры, или были произведены путем конкатенации).

3) Разрешение квадратного корня раздувает пространство поиска до бесконечности, так как это унарный оператор. Таким образом, вам понадобится способ ограничить количество применений, и я не уверен, что это будет (потеря точности, поскольку ответ приближается к 1, может быть?). Это еще одна причина, позволяющая только целочисленные промежуточные значения.

4) Экспоненциация будет быстро вызывать переполнение. 2^(9^(4^8)) слишком велика, чтобы хранить все цифры непосредственно [хотя в базе 2 это довольно очевидно, что они ;-)]. Поэтому вам придется либо принять, что вы можете пропустить решения с большими промежуточными значениями, либо вам придется написать кучу кода, чтобы выполнить арифметику с точки зрения факторов. Очевидно, что они не очень хорошо взаимодействуют с добавлением, поэтому вам, возможно, придется сделать некоторую оценку. Например, просто взглянув на величину числа факторов, мы видим, что 2^(9^(4^8)) нигде не близка (2^35), поэтому нет необходимости вычислять (2^(9^(4^8)) + 5)/(2^35). Это не может быть 29485235, даже если бы это было целое число (что, конечно же, нет, это другой способ исключить этот конкретный пример). Я думаю, что обработка этих чисел сложнее, чем остальная часть проблемы, вместе взятых, поэтому, возможно, вам следует ограничить себя однокнопочными полномочиями для начала и, возможно, результатами, которые соответствуют 64-битовому целому, в зависимости от того, какой язык вы используете.

5) Я забыл исключить тривиальное решение для любого ввода, просто конкатенируя все цифры. Это довольно легко обрабатывать, однако, просто поддерживайте параметр через рекурсию, которая сообщает вам, выполнили ли вы какие-либо операции, не связанные с конкатенацией маршрута, в вашу текущую подзадачу. Если вы этого не сделали, то проигнорируйте ложное совпадение.

Моя оценка из 6 цифр основана на том, что довольно легко написать решатель Countdown, который выполняется за долю секунды, даже если нет решения. Эта проблема отличается тем, что цифры должны использоваться по порядку, но есть больше операций (обратный отсчет не разрешает возведение в степень, квадратный корень или конкатенацию или нецелые промежуточные результаты). В целом я думаю, что эта проблема сопоставима, если вы решаете проблемы с квадратным корнем и переполнением. Если вы можете решить один случай за долю секунды, то вы можете перенаправить свой путь через миллион кандидатов в разумные сроки (при условии, что вы не против оставить свой компьютер).

На 10 цифр грубая сила представляется невозможной, поскольку вам необходимо рассмотреть 10 миллиардов случаев, каждый из которых требует значительного количества рекурсии.Поэтому, я думаю, вы столкнетесь с пределом грубой силы где-то между ними. Обратите внимание также, что мой простой алгоритм наверху все еще имеет много избыточности - он не останавливает вас (4,7,9,1) -> (47,9,1) -> (47, 0, 91), а затем и далее (4,7,9,1) -> (4,7,91) -> (47,91). Поэтому, если вы не выясните, где будут дублироваться эти дубликаты, и избегайте их, вы попытаетесь (47,91) дважды. Очевидно, что это не так много, когда в списке всего 2 числа, но когда в списке 7 номеров, вы, вероятно, не хотите, например, добавьте 4 из них вместе 6 различными способами, а затем разрешите полученную 4-балльную проблему 6 раз. Умность здесь не требуется для игры с обратным отсчетом, но для всех, что я знаю в этой проблеме, это может сделать разницу между грубым форсированием 8 цифр и грубым форсированием 9 цифр, что довольно важно.