Вычисление целевого номера из числа в наборе

Ответ 1

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

Прежде всего, если ваш набор имеет 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);
    }
}

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

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

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

В общем случае, если у вас есть операнды n+1 и должны вставлять операторы n, выбранные из возможностей k, тогда возможны (2n)!/n! 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);
    }
}

Ответ 5

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

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

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

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

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

Ответ 6

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

Основная идея такова: если задано множество чисел S, разделите S на два подмножества left и right всеми возможными способами (где нас не интересуют порядок или элементы в left и right), такие, что left и right являются непустыми. Теперь для каждого из этих разделов найдите все способы объединения элементов в 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

Ответ 7

код pusedo:

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 ...

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