Вычисления целевого числа от чисел в наборе

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

• Он рекурсивно генерирует все уравнения в постфиксной нотации
• Он также обеспечивает перевод из постфиксной нотации в инфиксную.
• Фактических арифметических вычислений не производится, поэтому вы должны реализовать это самостоятельно { {1}}
  • Будьте осторожны при делении на ноль.

С 4 операндами, 4 возможными операторами он генерирует все 7680 = 5 * 4! * 4 ^ 3 возможных выражений.

• 5 - каталонский (3). Каталанский (N) - это количество способов заключить в скобки N + 1 операнд.
• 4! поскольку 4 операнда являются перестановочными
• 4 ^ 3, потому что каждый из 3 операторов имеет 4 варианта выбора

Это определенно плохо масштабируется, поскольку количество выражений для N операндов равно [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].

В общем, если у вас есть n + 1 операндов и вы должны вставить n операторов, выбранных из k вариантов, то имеется (2n )! / п! k ^ n возможных уравнений.

Удачи!

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}

Вообще говоря, когда вам нужно сделать что-то рекурсивно, это помогает начать с «низа» и продумать свой путь вверх. Учтите: у вас есть набор S из n чисел {a, b, c, ...} и набор из четырех операции {+, -, *, /} . Давайте вызовем вашу рекурсивную функцию, которая работает с набором F (S)

• . Если n равно 1, то F (S) будет как раз этим числом.
• Если n равно 2, F (S) может состоять из восьми значений:
  • выберите левое число из S (2 варианта)
  • затем выберите операцию для применения (4 варианта)
  • ваше правое число будет тем, что осталось в наборе
• Теперь вы можете сделать обобщение из n = 2 case:
  • Выберите число x из S в качестве левого операнда ( n вариантов)
  • Выберите операцию для применения
  • ваш номер правой руки будет F (Sx)

Я позволю вам взять его отсюда. :)

править: Марк высказывает обоснованную критику; Вышеупомянутый метод не даст абсолютно всего. Чтобы решить эту проблему, вам нужно подумать об этом немного по-другому:

• На каждом шаге вы сначала выбираете операцию (4 варианта), а затем
• разбиваете S на два набора , для левого и правого операндов,
• и рекурсивно применить F к обоим разбиениям

Однако нахождение всех разбиений набора на 2 части само по себе нетривиально.

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

Основная идея заключается в следующем: дано множество S чисел, разделите S на два подмножества слева и справа всеми возможными способами (где нас не волнует порядок или элементы в слева и справа) так, чтобы слева и справа были непустыми. Теперь для каждого из этих разделов найдите все способы объединения элементов в left (рекурсивно!), и аналогично для right, и объедините два получившихся значения всеми возможными операторами. Рекурсия заканчивается, когда множество имеет только один элемент, и в этом случае возможно только одно значение.

Даже если вы не знаете Python, функция expressions должна быть достаточно простой для выполнения; функция splittings содержит некоторые странности Python, но все, что она делает, это находит все разбиения списка l на левые и правые части.

def splittings(l):
    n = len(l)
    for i in xrange(2**n):
        left = [e for b, e in enumerate(l) if i & 2**b]
        right = [e for b, e in enumerate(l) if not i & 2**b]
        yield left, right

def expressions(l):
    if len(l) == 1:
        yield l[0]
    else:    
        for left, right in splittings(l):
            if not left or not right:
                continue
            for el in expressions(left):
                for er in expressions(right):
                    for operator in '+-*/':
                        yield '(' + el + operator + er + ')'

for x in expressions('1234'):
    print x

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

Не хочу выдавать слишком много (в конце концов, это домашнее задание), но вы должны вызвать рекурсивную функцию, используя оператор, число и список, содержащий остальные числа. Рекурсивная функция извлечет число из списка и, используя переданную операцию, объединит его с переданным числом (которое является вашим текущим итогом). Возьмите полученный итог и снова вызовите себя с оставшимися элементами списка (вам придется итерировать список внутри вызова, но последовательность вызовов будет глубиной вперед). Сделайте это один раз для каждого из четырех операторов, если только успех не был достигнут предыдущим этапом поиска.

Я обновил это, чтобы использовать список вместо стека

Когда результатом операции будет ваше целевое число и ваш список будет пуст, значит, вы успешно нашли набор операций (те, которые проследили путь к успешному листу) - установите флаг Success и разворачивайтесь. Обратите внимание, что операторы не находятся ни в списке, ни в вызове: сама функция всегда выполняет итерацию по всем четырем операциям. Ваш механизм "разматывания" последовательности операторов от успешного листа для получения последовательности заключается в возврате текущего оператора и номера, добавленного к значению, возвращенному рекурсивным вызовом (только один из них будет успешным, поскольку вы остановились на успехе - очевидно, именно его и следует использовать). Если ни один из них не успешен, то то, что вы возвращаете, не имеет значения.

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

pusedo code:

Works(list, target)
for n in list
tmp=list.remove(n)
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ...

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

Прежде чем думать о том, как решить проблему (например, с графиками), действительно помогает просто посмотрите на проблему. Если вы застряли и не можете придумать какой-либо псевдокод, то, скорее всего, что-то вас сдерживает; Другой вопрос или беспокойство, которые еще не решены. Примером «липкого» вопроса в этом случае может быть: «Что именно является рекурсивным в этой проблеме?»

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

Вы хотите знать, дает ли какое-то выражение, использующее набор чисел (каждое число используется только один раз), целевое значение. Есть четыре бинарных операции, каждая из которых имеет обратную . Другими словами, вы хотите знать, дает ли первое число, оперируемое каким-либо выражением других чисел, цель. Другими словами, вы хотите знать, является ли какое-то выражение «других» чисел [...]. Если нет, то использование первой операции с первым номером на самом деле не дает вам того, что вам нужно, поэтому попробуйте другие операции. Если они не работают, то, возможно, этого просто не должно было быть.

Изменить: я подумал об этом для инфиксного выражения четырех операторов без скобок, поскольку в комментарии к исходному вопросу говорилось, что скобки были добавлены для примера (для ясности?), А скобки не использовались явно заявил.

Что ж, вы не упомянули об эффективности, поэтому я собираюсь опубликовать действительно грубое решение и позволить вам оптимизировать это, если хотите. Поскольку у вас могут быть скобки, его легко перебрать, используя Reverse Polish Notation :

Прежде всего, если в вашем наборе n чисел, вы должны использовать ровно n - 1 операторов. Таким образом, ваше решение будет дано последовательностью из 2n - 1 символов из {{ваш заданный набор}, {*, /, +, -}}

st = a stack of length 2n - 1
n = numbers in your set
a = your set, to which you add *, /, +, -
v[i] = 1 if the NUMBER i has been used before, 0 otherwise

void go(int k)
{
  if ( k > 2n - 1 ) 
  {
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you'll have to check that it is   
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on.

    return;
  }

  for ( each symbol x in a )
    if ( x isn't a number or x is a number but v[x] isn't 1 )
    {
      st[k] = x;
      if ( x is a number )
        v[x] = 1;

      go(k + 1);
    }
}