arrays - 使用基本操作的解决方案查找算法

Question

我需要制定算法方面的帮助。 我目前正在为我正在上的类(class)设计一些东西。

给定 4 个数字，我需要使用基本运算 (+-*/) 找到这 4 个数字的所有(或至少第一个)组合来得出某个答案。

例如，如果给定数字 [1,2,3,4]。 我必须回答12。 我可以看到(没有程序) (2-1)*3*4 = 12

但对于更复杂的数字，仅仅通过思考可能更难解决。 所以我需要一个程序来帮助我找到至少一种可能的组合来解决问题。

请注意，给定的4个号码中，号码可以重复，但每个号码只能使用一次。 例如，4 的集合可以是 [2,3,3,4]。但在该集合中，2 和 4 不能多次使用。

我最初的计划是暴力查找每 4 个数字的所有可能组合/顺序，然后迭代所有操作。我后来意识到这行不通，因为它没有考虑像 (1-2)*(3+4) 这样的操作。

所以我想知道是否有人知道我如何解决这个问题？

请记住，我对编程还很陌生，所以我可能不理解一些更高级的术语和功能。但我可以很好地掌握循环和数组等内容。

Answer 1

实际上没有那么多组合需要检查，因为优先案例的数量限制为 5:
((a:b):c):d
(a:b):(c:d)
(a:(b:c)):d
a:((b:c):d)
a:(b:(c:d))
因此，通过 24 种排列和 4 个可能的运算符的 3 个选择，可以得到 7680 种组合。其中许多组合实际上是相同的，因为在以下情况下优先级并不重要:
a+b+c+d
a+b+c-d
a*b*c*d
a*b*c/​​d

运行代码片段以查看一个简单的基于循环的算法，该算法检查这 7680 个组合的实际情况。对于 1:2:3:4=12 的情况，有数量惊人的解决方案。

function findArithmetic(target, numbers) {

    // PUT THE ARITHMETIC FUNCTIONS IN AN ARRAY, SO WE CAN ITERATE OVER THEM
    function sum(a, b) {return a + b}
    function dif(a, b) {return a - b}
    function prd(a, b) {return a * b}
    function div(a, b) {return a / b}
    var func = [sum, dif, prd, div];

    // DEFINE THE ORDER OF THE CALCULATIONS FOR THE 5 PRECEDENCE CASES
    var prec = [[0, 1, 4, 2, 5, 3],    // 0,1,2,3 are the four numbers
                [0, 1, 2, 3, 4, 5],    // 4 is the result of the 1st calculation
                [1, 2, 0, 4, 5, 3],    // 5 is the result of the 2nd calculation
                [1, 2, 4, 3, 0, 5],    // so here, do 1:2, then result1:3, then 0:result2
                [2, 3, 1, 4, 0, 5]];   // and here, do 2:3, then 1:result1, then 0:result2

    // FIND ALL PERMUTATIONS OF THE NUMBERS AND STORE THEM IN ARRAY "NUMS"
    var nums = [];
    for (var a = 0; a < 4; a++) {
        for (var b = 0; b < 4; b++) {
            if (a == b) continue;
            for (var c = 0; c < 4; c++) {
                if (a == c || b == c) continue;
                for (var d = 0; d < 4; d++) {
                    if (a == d || b == d || c == d) continue;
                    nums.push([numbers[a], numbers[b], numbers[c], numbers[d]]);
                }
            }
        }
    }

    // NOW GET DOWN TO BUSINESS
    var solutions = [];

    // ITERATE OVER ALL 24 PERMUTATIONS
    for (var n = 0; n < nums.length; n++) {

        // ITERATE OVER ALL 5 PRECEDENCE CASES
        for (var p = 0; p < 5; p++) {

            // ITERATE OVER THE 4 OPERATORS FOR THE FIRST CALCULATION
            for (var i = 0; i < 4; i++) {

                // ITERATE OVER THE 4 OPERATORS FOR THE SECOND CALCULATION
                for (var j = 0; j < 4; j++) {

                    // ITERATE OVER THE 4 OPERATORS FOR THE THIRD CALCULATION
                    for (var k = 0; k < 4; k++) {

                        // DO THE CALCULATIONS
                        nums[n][4] = func[i](nums[n][prec[p][0]], nums[n][prec[p][1]]);
                        nums[n][5] = func[j](nums[n][prec[p][2]], nums[n][prec[p][3]]);
                        var result = func[k](nums[n][prec[p][4]], nums[n][prec[p][5]]);

                        // IF THE RESULT IS CORRECT, MAKE A STRING AND ADD TO SOLUTIONS
                        if (result == target) {
                            solutions.push(makeString(n, p, i, j, k));
                        }
                    }
                }
            }
        }
    }
    return solutions;

    // TURN THE RESULT INTO A PRESENTABLE STRING
    // this is a bit fiddly, because in each precedence case, the calculations are done in a different order
    function makeString(n, p, i, j, k) {
        // CHOOSE THE RIGHT STRING TEMPLATE, BASED ON THE PREFERENCE CASE
        var str = ["((aAb)Bc)Cd", "(aAb)B(cCd)", "(aA(bBc))Cd", "aA((bBc)Cd)", "aA(bB(cCd))"][p];
        // REPLACE "a", "b", "c", AND "d" WITH THE NUMBERS
        for (var c = 0; c < 4; c++) str = str.replace(["a","b","c","d"][c], nums[n][c]);
        // REPLACE "A", "B" AND "C" WITH THE OPERATORS, BASED ON EXECUTION ORDER IN PREFERENCE CASE
        var order = [["A","B","C"], ["A","C","B"], ["B","A","C"], ["B","C","A"], ["C","B","A"]];
        for (var c = 0; c < 3; c++) str = str.replace(order[p][c], ["+","-","*","/"][[i,j,k][c]]);
        return str + "=" + target;
    }
}

// RUN THE FUNCTION AND DISPLAY THE RESULTS IN THE CONSOLE
var sol = findArithmetic(12, [1,2,3,4]);
document.write(sol.length + " solutions found:<BR><PRE>");
for (var s in sol) document.write(sol[s] + "<BR>");

这是一个更简单的解决方案，没有优先级数组。它单独写出了五个优先案例的计算。通常程序员会认为这是一个不优雅的解决方案，因为它打破了“不要重复自己”的规则；然而，在这种情况下，它使代码更容易理解，并且大大简化了结果的显示，所以这一次我认为这样做是有意义的。

此版本仅针对每个数字排列和运算符组合返回一个解决方案，因为具有不同括号位置的解决方案，例如 (a*b)+(c-d) 和 ((a *b)+c)-d，实际上只是重复。 (这就是每次计算后的 continue 语句的用途。)

function findArithmetic(target, numbers) {

    // PUT THE ARITHMETIC FUNCTIONS IN AN ARRAY, SO WE CAN ITERATE OVER THEM
    function sum(a, b) {return a + b}
    function dif(a, b) {return a - b}
    function prd(a, b) {return a * b}
    function div(a, b) {return a / b}
    var func = [sum, dif, prd, div];

    // FIND ALL PERMUTATIONS OF THE NUMBERS AND STORE THEM IN ARRAY "NUMS"
    var nums = [];
    for (var a = 0; a < 4; a++) {
        for (var b = 0; b < 4; b++) {
            if (a == b) continue;
            for (var c = 0; c < 4; c++) {
                if (a == c || b == c) continue;
                for (var d = 0; d < 4; d++) {
                    if (a == d || b == d || c == d) continue;
                    nums.push([numbers[a], numbers[b], numbers[c], numbers[d]]);
                }
            }
        }
    }

    // NOW GET DOWN TO BUSINESS
    var solutions = [];
    var op = ["+","-","*","/"];

    // ITERATE OVER ALL 24 PERMUTATIONS
    for (var n = 0; n < nums.length; n++) {
        var a = nums[n][0], b = nums[n][1], c = nums[n][2], d = nums[n][3];

        // ITERATE OVER THE 4 OPERATORS FOR THE FIRST CALCULATION
        for (var i = 0; i < 4; i++) {

            // ITERATE OVER THE 4 OPERATORS FOR THE SECOND CALCULATION
            for (var j = 0; j < 4; j++) {

                // ITERATE OVER THE 4 OPERATORS FOR THE THIRD CALCULATION
                for (var k = 0; k < 4; k++) {

                    // CHECK PRECEDENCE CASE 1:  ((a:b):c):d
                    if (target == func[k](func[j](func[i](a, b), c), d)) {
                        solutions.push("((" + a + op[i] + b + ")" + op[j] + c + ")" + op[k] + d + "=" + target);
                        continue;
                    }
                    // CHECK PRECEDENCE CASE 2:  (a:b):(c:d)
                    if (target == func[j](func[i](a, b), func[k](c, d))) {
                        solutions.push("(" + a + op[i] + b + ")" + op[j] + "(" + c + op[k] + d + ")=" + target);
                        continue;
                    }
                    // CHECK PRECEDENCE CASE 3:  (a:(b:c)):d
                    if (target == func[k](func[i](a, func[j](b, c)), d)) {
                        solutions.push("(" + a + op[i] + "(" + b + op[j] + c + "))" + op[k] + d + "=" + target);
                        continue;
                    }
                    // CHECK PRECEDENCE CASE 4:  a:((b:c):d)
                    if (target == func[i](a, func[k](func[j](b, c), d))) {
                        solutions.push(a + op[i] + "((" + b + op[j] + c + ")" + op[k] + d + ")=" + target);
                        continue;
                    }
                    // CHECK PRECEDENCE CASE 5:  a:(b:(c:d))
                    if (target == func[i](a, func[j](b, func[k](c, d)))) {
                        solutions.push(a + op[i] + "(" + b + op[j] + "(" + c + op[k] + d + "))=" + target);
                    }
                }
            }
        }
    }
    return solutions;
}

// RUN THE FUNCTION AND DISPLAY THE RESULTS IN THE CONSOLE
var sol = findArithmetic(2, [4,5,6,12]);
document.write(sol.length + " solutions found:<BR><PRE>");
for (var s in sol) document.write(sol[s] + "<BR>");