алгоритм комбинирования чисел

Question

Напишите функцию, которая содержит строку цифр и целевое значение, печатает, где ставить «+» и «*» между цифрами, чтобы они точно совмещались с целевым значением. Обратите внимание, что может быть более одного ответа, не имеет значения, какой вы печатаете.

Примеры:

"1231231234",11353 -> "12*3+1+23*123*4" 
"3456237490",1185  -> "3*4*56+2+3*7+490" 
"3456237490",9191  -> "no solution"

Answer 1

Если у вас есть N-значное значение, есть N-1 возможных слотов для операторов + или *. Итак, грубая сила, есть 3 ^ (N-1) возможностей. Тестирование всего этого неэффективно.

НО

Все ваши примеры состоят из 10 цифр. 3 ^ 9 = 19683, так что грубая сила прекрасна! Не нужно любить.

Итак, все, что вам нужно сделать, - это перебрать все 19683 случая, каждый раз создавая строку для этого случая и оценивая выражение. Оценка выражения является простой задачей. Итерация проста (просто используйте возрастающее значение, вы можете прочитать состояние первого слота по (i% 3), что дает вам «без оператора» «+» или «*», состояние второго слота: (i / 3)% 3, состояние третьего слота: (i / 9)% 3 и т. Д.)

Даже с грубым кодом синтаксического анализа процессоры работают быстро.

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

Answer 2

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

Answer 3

В Google Code Jam была расширенная версия этой проблемы в прошлом году (в Round 1C ), называемая Ugly Numbers. Вы можете перейти по этой ссылке и щелкнуть «Анализ контестов», чтобы узнать о некоторых подходах к этой проблеме, когда она распространяется на большое количество цифр.

Answer 4

«Умнее» подход (с использованием динамического программирования) в основном это:

Для каждой подстроки исходной строки определите все возможные значения, которые она может создать. (например, в вашем первом примере «12» может принимать значение 1 + 2 = 3 или 1 * 2 = 2)

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

Таким образом, когда вы добавляете «+» или «*», вы можете представить его как объединение двух подстрок строки. (и поскольку у вас есть возможные значения для каждой подстроки, вы можете увидеть, возможна ли такая комбинация)

Эти значения могут быть сгенерированы аналогично: попробуйте разбить подстроку всеми возможными способами и объединить различные значения в каждой половине подстроки.

Таким образом, общее число «состояний» примерно соответствует | S | ^ 2 * target - для вашего примера это на хуже , чем метод грубой силы. Но если бы у вас была строка длиной 1000 и целевое значение, скажем, 5000, то проблема была бы решена с помощью динамического программирования.

Answer 5

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