Руководство по алгоритмическому мышлению (уравнение четырех четвертей)

Question

Недавно я увидел логическую/математическую задачу 4 Fours, где вам нужно было использовать 4 четверки и ряд операторов для создания уравнений, равных целым числам от 0 до N.

Как вы собираетесь писать элегантный алгоритм, чтобы придумать первые 100 ...

Я начал с создания базовых расчетов, таких как 4-4, 4 + 4, 4x4, 4/4, 4 !, Sqrt 4 и сделал эти значения целыми числами.

Однако я понял, что это будет скотина метод силы тестирования комбинации, чтобы увидеть, если они равны, то 0 1, затем 2, затем 3 и т.д. ...

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

Любая помощь в том, как подойти к проблеме типа это было бы полезно ... не фактический код ... но как продумать эту проблему

Спасибо!

Answer 1

Это интересная проблема. Здесь есть несколько разных вещей. Одна из проблем заключается в том, как описать последовательность операций и операндов, которые входят в арифметическое выражение. Использование скобок для установления порядка операций довольно беспорядочно, поэтому вместо этого я предлагаю думать о выражении как стек операций и операндов, например - 4 4 для 4-4, + 4 * 4 4 для (4 * 4) +4, * 4 + 4 4 для (4 + 4)) * 4 и т. Д. Это как обратная польская нотация на калькуляторе HP. Тогда вам не нужно беспокоиться о круглых скобках, поскольку структура данных для выражений поможет ниже, когда мы создадим более крупные и большие выражения.

Теперь перейдем к алгоритму построения выражений. Динамическое программирование в этой ситуации не работает, на мой взгляд, потому что (например) для построения некоторых чисел в диапазоне от 0 до 100 вам может потребоваться временно выйти за пределы этого диапазона.

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

Каждый узел (число) на графике имеет связанный с ним вес, минимальное количество 4, необходимое для достижения этого узла, а также выражение, которое достигает этого результата. Сначала вы начинаете только с узла (4), с номером 1, связанным с ним (требуется 4, чтобы сделать 4), и простым выражением «4». Вы также можете бросить (44) весом 2, (444) весом 3 и (4444) с весом 4.

Чтобы создать более крупные выражения, примените все различные операции, которые у вас есть к этим начальным узлам.Например, унарное отрицание, факторный, квадратный корень; двоичные операции, такие как * 4 в нижней части вашего стека для умножения на 4, + 4, - 4, / 4, ^ 4 для возведения в степень, а также + 44 и т. д. Вес операции - это число 4s, необходимое для этой операции; унарные операции имели бы вес 0, + 4 имел бы вес 1, * 44 имел бы вес 2 и т. д. Вы бы добавили вес операции к весу узла, на котором он работает, чтобы получить новый вес, например, + 4 на узле (44) с весом 2, а выражение «44» приведет к новому узлу (48) с весом 3 и выражению «+ 4 44». Если результат для 48 имеет лучший вес, чем существующий результат для 48, замените этот новый узел на (48).

При применении функций вам придётся использовать определенный смысл. факторный (4444) был бы очень большим числом; было бы разумно установить домен для вашей факториальной функции, который помешал бы получить слишком большой результат или выйти за рамки. То же самое с функциями типа/4; если вы не хотите иметь дело с дробями, скажите, что несимволы 4 находятся за пределами области/4 и в этом случае не применяют оператор.

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

Answer 2

Я думаю, что решение грубой силы - это единственный путь.
Причина в том, что каждый номер имеет другой способ добраться до него, и получение определенного x может не иметь ничего общего с получением x+1.

Сказав это, вы можете сделать решение грубой силы более быстрым, если возможно, с помощью очевидных ходов.
Например, если я до 20 с помощью «4» три раза (4*4+4), то очевидно, чтобы добраться до 16, 24 и 80. Проведения массива из 100 бит и маркировки число достигло

Answer 3

Аналогичны подмножества проблема сумма, она может быть решена с помощью Dynamic Programming (DP), следуя рекурсивные формулы:

D(0,0) = true 
D(x,0) = false  x!=0 
D(x,i) = D(x-4,i-1) OR D(x+4,i-1) OR D(x*4,i-1) OR D(x/4,i-1) 

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

Преимущество этого метода (при использовании с DP) заключается в том, что вы не пересчитываете несколько значений более одного раза. Я не уверен, что это будет эффективно для 4 4-х, но я считаю, что теоретически это может стать значительным улучшением для менее ограниченного обобщения этой проблемы.

Answer 4

Этот ответ является просто расширением Amit's. По сути, ваши операции:

1. Применить унарный оператор к существующему выражению, чтобы получить новое выражение (это не использует никакого дополнительный 4с)
2. Применить бинарный оператор на два существующие выражения, чтобы получить новый выражение (новое выражение имеет число 4s, равное сумме двух входных выражений)

Для каждого n от 1 ..4, вычислить Expressions(n) - список (Выражение, значение) пара следующим образом: (При фиксированном n, только магазин 1 выражение в списке, который принимает значение любого заданного значения)

1. Инициализировать список с конкатенацией из n 4s (т.е. 4, 44, 444, 4444)
2. Для i от 1 до n-1, и каждый из разрешенных бинарный оператор op, добавить выражение (и значение) e1 op e2, где e1 находится в Expressions(i) и e2 находится в Expressions(n-i)
3. Неоднократно применяют унарные операторы к выражениям/значениям, вычисленным до сих пор на этапах 1-3. Когда останавливать (применяя 3 рекурсивно) немного расплывчато, обязательно остановитесь, если итерация не производит новых значений. Потенциально ограничьте величину допустимых значений или размер выражений.

Пример унарные операторы !, Sqrt, - и т.д. Пример бинарных операторов +-*/^ и т.д. Вы можете легко распространить этот подход к операторам с большим количеством аргументов, если это разрешено.

Вы можете сделать что-то более умное с точки зрения шага 3, никогда не заканчивающегося ни для какого n. Простой способ (описанный выше) не начинает вычислять Expressions(i) до тех пор, пока Expressions(j) не будет заполнен для всех j < i. Это требует, чтобы мы знали, когда остановиться. Альтернативой является создание выражений определенной максимальной длины для каждого n, тогда, если вам нужно (потому что вы не нашли определенные значения), увеличьте максимальную длину во внешнем цикле.