Для чисел примерно до 6 цифр или около того, я бы сказал, грубо говоря, по следующей схеме:
1) Разбейте ваше начальное значение на список (массив, в зависимости от языка) чисел. Изначально это цифры.
2) Для каждой пары чисел сложите их вместе, используя один из операторов. Если результат - целевое число, верните успех (и распечатайте все операции, выполненные на вашем выходе). В противном случае, если это целое число, вернитесь в новый, меньший список, состоящий из числа, которое вы только что рассчитали, и чисел, которые вы не использовали. Или вы можете разрешить нецелочисленные промежуточные результаты, которые сделают пространство поиска несколько больше. Двоичные операции:
- Добавить
- 1010 * вычесть *
- 1012 * умножить *
- разделяй
- мощность
- конкатенация (которая может использоваться только для чисел, которые являются либо исходными цифрами, либо были получены путем конкатенации).
3) Разрешение квадратного корня увеличивает пространство поиска до бесконечности, так как это унарный оператор. Таким образом, вам понадобится способ ограничить число случаев его применения, и я не уверен, что это будет (потеря точности, когда ответ приближается к 1, может быть?). Это еще одна причина, по которой допускаются только целочисленные промежуточные значения.
4) Возведение в степень быстро вызовет переполнение. 2 ^ (9 ^ (4 ^ 8)) слишком велик, чтобы хранить все цифры напрямую [хотя в базе 2 довольно очевидно, что они есть ;-)]. Таким образом, вы либо должны будете признать, что вы можете пропустить решения с большими промежуточными значениями, либо вам придется написать кучу кода, чтобы выполнить свою арифметику с точки зрения факторов. Очевидно, что они не очень хорошо взаимодействуют с дополнением, поэтому вам, возможно, придется сделать некоторую оценку. Например, просто взглянув на величину числа факторов, мы увидим, что 2 ^ (9 ^ (4 ^ 8)) далеко не рядом (2 ^ 35), поэтому нет необходимости вычислять (2 ^ (9 ^ ( 4 ^ 8)) + 5) / (2 ^ 35). Это не может быть 29485235, даже если бы это было целое число (а это, безусловно, не так - еще один способ исключить этот конкретный пример). Я думаю, что работать с этими числами сложнее, чем с остальными проблемами, вместе взятыми, поэтому, возможно, вам следует ограничить себя однозначными степенями для начала и, возможно, результатами, которые соответствуют 64-битному целому числу, в зависимости от того, какой язык вы используете. 1023 *
5) Я забыл исключить тривиальное решение для любого ввода, просто конкатенировать все цифры. Это довольно легко обработать, однако, просто сохраняйте параметр с помощью рекурсии, которая сообщает вам, выполнили ли вы какие-либо неконкатенационные операции на пути к вашей текущей подзадаче. Если нет, игнорируйте ложное совпадение.
Моя оценка в 6 цифр основана на том факте, что довольно просто написать решатель Обратный отсчет , который запускается за доли секунды, даже когда решения не существует. Эта проблема отличается тем, что цифры должны использоваться по порядку, но есть больше операций (обратный отсчет не допускает возведения в степень, квадратного корня или конкатенации или нецелых промежуточных результатов). В целом, я думаю, что эта проблема сопоставима, если вы решите проблемы с квадратным корнем и переполнением. Если вы сможете решить одно дело за долю секунды, то вы сможете перебрать миллион кандидатов в разумные сроки (если вы не против оставить свой компьютер включенным).
Из 10 цифр грубая сила кажется невозможной, потому что вам нужно рассмотреть 10 миллиардов случаев, каждый из которых требует значительного количества рекурсии. Так что, думаю, вы достигнете предела грубой силы где-то между ними.
Обратите внимание, что мой простой алгоритм в верхней части все еще имеет большую избыточность - он не мешает вам делать (4,7,9,1) -> (47,9,1) -> (47,91 ), а затем и позже (4,7,9,1) -> (4,7,91) -> (47,91). Так что, если вы не определитесь, где эти дубликаты возникнут, и избегите их, вы попытаетесь (47,91) дважды. Очевидно, что это не так много работы, когда в списке только 2 числа, но когда в списке 7 номеров, вы, вероятно, не хотите, например, сложите 4 из них 6 различными способами, а затем решите полученную проблему с 4 числами 6 раз. Хитрость здесь не требуется для игры «Обратный отсчет», но, насколько мне известно, в этой задаче может иметь значение разница между 8-значными и 9-значными брут-форсами, что весьма важно.