使用基本操作的解决方案查找算法 [英] Solution finder algorithm using basic operations

查看：107 发布时间：2015/11/30 21:38:04 arrays algorithm loops math combinatorics

本文介绍了使用基本操作的解决方案查找算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我需要做的算法帮助。我目前正在设计的东西的一类，我服用。

由于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）。

所以我想知道如果任何人有如何我可以接近解决这一问题的想法？

请记住，那我还是相当新的编程，所以我可能不理解一些更高级的条件和功能。但我能跟上pretty的好了这些东西，循环和数组。

解决方案

有没有实际的多种组合进行检查，因为precedence案件的数量限制为5：
（（A：B）：C）：D
（A：B）：C：D）
（答：（B：C））：D
A：（（B：C）：D）
A：（B：（C：D））
所以24排列3的选择，从4个可能的运营商，这给7680的组合。而很多这些组合都几乎一模一样，因为precedence是不重要的类似情况：
A + B + C + D
A + B + C-D
A * B * C * D
A * B * C / D

运行code段看到一个简单的循环为基础的算法，检查这些7680组合在行动。有解决方案的情况下数量惊人 1：2：3：4 = 12

函数findArithmetic（目标数）{

    //使运算功能在一个阵列，这样我们就可以在它们之间迭代
    功能总和（A，B）{返回A + B}
    功能DIF（A，B）{返回 -  B}
    功能PRD（A，B）{返回A * B}
    功能分区（A，B）{返回A / B}
    VAR FUNC =总和，DIF，珠三角，DIV]。

    //定义计算的为了使5 preCEDENCE案例
    变种$ P $件= [[0，1，4,2，5,3]，// 0,1,2,3是四个数字
                [0，1，2，3，4，5]，// 4是第一计算的结果
                并[1,2，0，4，5，3] // 5是第二计算的结果
                [1，2，4，3,0，5]，//所以在这里，执行1：2，然后RESULT1：3，然后0：RESULT2
                [2，3，1，4,0，5]]; //这里，做2：3，则1：RESULT1，然后0：RESULT2

    //发现号的所有排列，并将其存储阵列NUMS
    VAR NUMS = [];
    为（变种一个= 0;一个4;;一个++）{
        为（变种B = 0; b将4; b ++）{
            若（a == b）继续;
            为（变种C = 0; C＆LT; 4，C ++）{
                若（a ==ç|| b == c）继续;
                为（变种d = 0表示d的4;; d ++）{
                    如果（A = D || b = D ||ç== d）继续;
                    nums.push（[号码并[a]，数字并[b]，数字并[c]，数字并[d]]）;
                }
            }
        }
    }

    //现在降到正事
    变种溶液= [];

    //遍历所有24排列
    为（变种N = 0; N＆LT; nums.length; N ++）{

        //遍历所有5 preCEDENCE案例
        为（变种p = 0时，P小于5，P ++）{

            //遍历4运营商对于第一种计算法
            为（变种I = 0; I＆4;;我++）{

                //遍历4运营商对于第二种计算方法
                为（变种J = 0; J＆4;; J ++）{

                    //遍历条经营者为第三计算
                    为（变种K = 0; K＆4;; k ++）{

                        // DO计算
                        NUMS [n]的[4] = FUNC [I]（NUMS [n]的[$ P $件[P] [0]]，NUMS [n]的[$ P $件[P] [1]]）;
                        NUMS [n]的[5] = FUNC [j]的（NUMS [n]的[$ P $件[P] [2]]，NUMS [n]的[$ P $件[P] [3]]）;
                        变种结果= FUNC [k]的（NUMS [n]的[$ P $件[P] [4]]，NUMS [n]的[$ P $件[P] [5]]）;

                        //如果结果是正确的，使字符串，并加入到解决方案
                        如果（结果==目标）{
                            solutions.push（makeString（N，P，I，J，K））;
                        }
                    }
                }
            }
        }
    }
    返回的解决方案;

    //关闭结果放入一个preSENTABLE STRING
    //这有点繁琐，因为在每precedence情况下，计算以不同的顺序进行
    功能makeString（N，P，I，J，K）{
        //选择合适的字符串模板的基础上，preFERENCE CASE
        VAR海峡= [（（AAB）BC）CD，（AAB），B（CCD），（AA（BBC））CD，AA（（BBC）光盘版），AA（BB（CCD ））] [P];
        // REPLACE一个，B，C，和d与数字
        为（变种C = 0; C＆LT; 4，C ++）海峡= str.replace（[A，B，C，D] [C]，NUMS [N] [C]）;
        //将A，B和C与运营商的基础上，执行顺序preFERENCE CASE
        VAR为了= [[A，B，C]，[A，C，B]，[B，A，C]，[B ，C，A]，[C，B，A]];
        为（变种C = 0; C＆LT; 3，C ++）海峡= str.replace（顺序[P] [C]，[+， - ，*，/] [[I，J中，k]并[c]]）;
        返回STR +=+目标;
    }
}

//运行函数，并显示在控制台结果
变种溶胶= findArithmetic（12，[1,2,3,4]）;
（找到的解决办法;见控制台的详细资料。sol.length +）警告;
如果（sol.length == 0）的console.log（没有找到解决方案）
其他的（VAR S在SOL）的console.log（溶胶[S]）;

这是一个简单的解决方案，而不precedence阵列。它的计算写出来单独五precedence案件。通常程序员会认为这是一个unelegant解决方案，因为它打破了不要重复自己的规则;然而，在这种情况下，它使code更容易理解，而且大大简化了结果的显示，所以这一次我觉得是有意义的做这种方式。

该版本只返回％的数字和运算符的组合排列一个解决方案，因为不同的支架放置，如（A * B）+解决方案（CD）和（（A * B）+ C）-d ，其实只是重复。（这就是每一个计算后的继续语句是。）

函数findArithmetic（目标数）{

    //使运算功能在一个阵列，这样我们就可以在它们之间迭代
    功能总和（A，B）{返回A + B}
    功能DIF（A，B）{返回 -  B}
    功能PRD（A，B）{返回A * B}
    功能分区（A，B）{返回A / B}
    VAR FUNC =总和，DIF，珠三角，DIV]。

    //发现号的所有排列，并将其存储阵列NUMS
    VAR NUMS = [];
    为（变种一个= 0;一个4;;一个++）{
        为（变种B = 0; b将4; b ++）{
            若（a == b）继续;
            为（变种C = 0; C＆LT; 4，C ++）{
                若（a ==ç|| b == c）继续;
                为（变种d = 0表示d的4;; d ++）{
                    如果（A = D || b = D ||ç== d）继续;
                    nums.push（[号码并[a]，数字并[b]，数字并[c]，数字并[d]]）;
                }
            }
        }
    }

    //现在降到正事
    变种溶液= [];
    变种运算= [+， - ，*，/];

    //遍历所有24排列
    为（变种N = 0; N＆LT; nums.length; N ++）{
        变种一个= NUMS [n]的[0]，B = NUMS [n]的[1]中，c = NUMS [n]的[2]，D = NUMS [n]的[3];

        //遍历4运营商对于第一种计算法
        为（变种I = 0; I＆4;;我++）{

            //遍历4运营商对于第二种计算方法
            为（变种J = 0; J＆4;; J ++）{

                //遍历条经营者为第三计算
                为（变种K = 0; K＆4;; k ++）{

                    //检查preCEDENCE案例1：（（A：B）：C）：D
                    如果（目标== FUNC [K]（FUNC [J]（FUNC [I]（A，B），C），D））{
                        solutions.push（（（+ A +运算[I] + B +）+运算[j]的+ C +）+运算[K] + D +=+靶）;
                        继续;
                    }
                    //检查preCEDENCE案例2：（A：B）：C：D）
                    如果（目标== FUNC [J]（FUNC [I]（A，B），FUNC [K]（C，D）））{
                        solutions.push（（+ A +运算[I] + B +）+运算[j]的+（+ C +运算[K] + D +）=+靶）;
                        继续;
                    }
                    //检查preCEDENCE案例3：（A：（B：C））：D
                    如果（目标== FUNC [K]（FUNC [I]（A，FUNC [J]（B，C）），D））{
                        solutions.push（（+ A + OP [我] +（+ B +运算[J] + C +））+ OP [K] + D +=+目标）;
                        继续;
                    }
                    //检查preCEDENCE案例4：：（（B：C）：D）
                    如果（目标== FUNC [I]（A，FUNC [K]（FUNC [J]（B，C），D）））{
                        solutions.push（A +运[I] +（（+ B +运算[j]的+ C +）+运算[K] + D +）=+靶）;
                        继续;
                    }
                    //检查preCEDENCE案例5：：（B：（C：D））
                    如果（目标== FUNC [I]（A，FUNC [J]（B，FUNC [K]（C，D））））{
                        solutions.push（A + OP [我] +（+ B +运算[J] +（+ C + OP [K] + D +））=+目标）;
                    }
                }
            }
        }
    }
    返回的解决方案;
}

//运行函数，并显示在控制台结果
变种溶胶= findArithmetic（2，[4,5,6,12]）;
（找到的解决办法;见控制台的详细资料。sol.length +）警告;
如果（sol.length == 0）的console.log（没有找到解决方案）
其他的（VAR S在SOL）的console.log（溶胶[S]）;

I need help with making an algorithm. I am currently designing something for a class I am taking.

Given 4 numbers, I need to find all (or at least the first) combination of the 4 numbers using basic operations (+-*/) to make a certain answer.

For example, if given numbers [1,2,3,4]. and I have to make the answer 12. I can see (without a program) that (2-1)*3*4 = 12

But for more complex numbers, it may be harder to solve just by thinking about it. So I require a program to help me find at least one possible combination to solve the problem.

Note that, in the given 4 numbers, the numbers may repeat, but each number can only used once. For example, the set of 4 can be [2,3,3,4]. But in that set, 2 and 4 cannot be used more than once.

I originally had a plan to brute force find all the possible combinations/orders of each 4 numbers, then iterating through all the operations. I later realized that this won't work as it doesn't take into account an operations like (1-2)*(3+4).

So I was wondering if anyone had an idea of how I can approach solving this problem?

Please keep in mind, that I am still fairly new to programming, so I may not understand some of the more advanced terms and functions. But I can keep up pretty well with things like loops and arrays.

解决方案

There aren't actually that many combinations to check, because the number of precedence cases is limited to 5:
((a:b):c):d
(a:b):(c:d)
(a:(b:c)):d
a:((b:c):d)
a:(b:(c:d))
so with 24 permutations and 3 choices from 4 possible operators, that gives 7680 combinations. And many of these combinations are really identical, because the precedence is unimportant in cases like:
a+b+c+d
a+b+c-d
a*b*c*d
a*b*c/d

Run the code snippet to see a simple loop-based algorithm which checks these 7680 combinations in action. There are a surprising number of solutions for the case 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]);
alert(sol.length + " solutions found; see console for details.");
if (sol.length == 0) console.log("no solutions found")
else for (var s in sol) console.log(sol[s]);

This is a simpler solution, without the precedence array. It has the calculations for the five precedence cases written out seperately. Usually programmers would consider this an unelegant solution, because it breaks the "don't repeat yourself" rule; however, in this case it makes the code much easier to understand, and it greatly simplifies the displaying of the results, so for once I think it makes sense to do it this way.

This version only returns one solution per permutation of the numbers and combination of operators, because solutions with different bracket placement, like (a*b)+(c-d) and ((a*b)+c)-d, are really just duplicates. (That's what the continue statement after each calculation is for.)

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]);
alert(sol.length + " solutions found; see console for details.");
if (sol.length == 0) console.log("no solutions found")
else for (var s in sol) console.log(sol[s]);

这篇关于使用基本操作的解决方案查找算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

使用基本操作的解决方案查找算法 [英] Solution finder algorithm using basic operations

问题描述

相关文章

C/C++最新文章

热门教程

热门工具

登录关闭

使用基本操作的解决方案查找算法 [英] Solution finder algorithm using basic operations

问题描述

相关文章

C/C++最新文章

热门教程

热门工具

登录 关闭

登录关闭