algorithm - 从一组数字中计算目标数字

Question

我正在做一个家庭作业问题，它问我这个问题:

给定一组有限的数字和一个目标数字，使用基本数学运算(add、sub、mult、div)并使用集合中的每个数字，找出该集合是否可用于计算目标数字 exactly一次(所以我需要用尽集合)。这必须通过递归来完成。

所以，例如，如果我有集合

{1, 2, 3, 4}

和目标 10，然后我可以通过使用

((3 * 4) - 2)/1 = 10. 

我正在尝试用伪代码来表达该算法，但到目前为止还没有走得太远。我在想图表是要走的路，但绝对会感谢这方面的帮助。谢谢。

Answer 1

这并不是最快的解决方案，而是一个有启发性的解决方案。

• 它递归地生成后缀符号中的所有方程
• 它还提供了从后缀到中缀符号的转换
• 没有完成实际的算术计算，所以你必须自己实现
  • 小心被零除

有 4 个操作数，4 个可能的运算符，它生成所有 7680 = 5 * 4! * 4^3 可能的表达方式。

• 5 是加泰罗尼亚语 (3)。 Catalan(N) 是对 N+1 个操作数进行组合的方式数。
• 4!因为 4 个操作数是可置换的
• 4^3因为3个算子各有4个选择

这绝对不能很好地扩展，因为 N 个操作数的表达式数量是 [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...]。

通常，如果您有 n+1 个操作数，并且必须插入从 k 种可能性中选择的 n 个运算符，则有 (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);
    }
}