使用基本操作的解决方案查找器算法
Solution finder algorithm using basic operations
我需要帮助来制作算法。
我目前正在为我正在参加的 class 设计一些东西。
给定 4 个数字，我需要使用基本运算 (+-*/) 找到这 4 个数字的所有（或至少第一个）组合来得出某个答案。
例如，如果给定数字 [1,2,3,4]。
我必须回答 12。
我可以看到（没有程序） (2-1)*3*4 = 12
但对于更复杂的数，光靠想可能更难解。 所以我需要一个程序来帮助我找到至少一种可能的组合来解决问题。
注意，在给定的4个号码中，号码可以重复，但每个号码只能使用一次。
例如，4 的集合可以是 [2,3,3,4]。但是在那个集合中，2和4不能使用超过一次。
我本来打算暴力破解每4个数的所有可能combinations/orders，然后遍历所有的操作。后来我意识到这行不通，因为它没有考虑 (1-2)*(3+4).
这样的操作
所以我想知道是否有人知道我可以如何解决这个问题？
请记住，我对编程还很陌生，所以我可能不理解一些更高级的术语和函数。但是我可以跟上循环和数组之类的东西。
您正在寻找 binary expression trees 4 片叶子。始终有一个顶级节点（在您的情况下为 +、*、-、/）。对于给定的顶级节点，根据顶级节点左侧的叶子数量组织搜索，该数量必须是 1 到 3 范围内的数字。有一个自然的递归解决方案，例如，如果左边有三片叶子那么它本身就是一棵三片叶子的二叉表达式树。你真的不需要使用树数据结构 - 你可以使用完全括号字符串（例如像“（（（1 + 2）* 3）/ 4）”对于顶部节点是“/”的树，它的左边side 是树 "((1 + 2)*3)" 右边是叶子 4).
实际上要检查的组合并不多，因为优先案例的数量限制为 5:
((a:b):c):d
(a:b):(c:d)
(a:(b:c)):d
a:((b:c):d)
a:(b:(c:d))
因此，从 4 种可能的运算符中进行 24 种排列和 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>");
这是一个更简单的解决方案，没有优先级数组。它有单独写出的五个优先案例的计算。通常程序员会认为这是一个不优雅的解决方案，因为它违反了 "don't repeat yourself" 规则；然而，在这种情况下，它使代码更容易理解，并且大大简化了结果的显示，所以我认为这样做是有道理的。
这个版本只有 returns 每个数字排列和运算符组合的解决方案，因为括号位置不同的解决方案，如 (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>");
我需要帮助来制作算法。 我目前正在为我正在参加的 class 设计一些东西。
给定 4 个数字，我需要使用基本运算 (+-*/) 找到这 4 个数字的所有（或至少第一个）组合来得出某个答案。
例如，如果给定数字 [1,2,3,4]。 我必须回答 12。 我可以看到（没有程序） (2-1)*3*4 = 12
但对于更复杂的数，光靠想可能更难解。 所以我需要一个程序来帮助我找到至少一种可能的组合来解决问题。
注意，在给定的4个号码中，号码可以重复，但每个号码只能使用一次。 例如，4 的集合可以是 [2,3,3,4]。但是在那个集合中，2和4不能使用超过一次。
我本来打算暴力破解每4个数的所有可能combinations/orders，然后遍历所有的操作。后来我意识到这行不通，因为它没有考虑 (1-2)*(3+4).
这样的操作所以我想知道是否有人知道我可以如何解决这个问题？
请记住，我对编程还很陌生，所以我可能不理解一些更高级的术语和函数。但是我可以跟上循环和数组之类的东西。
您正在寻找 binary expression trees 4 片叶子。始终有一个顶级节点（在您的情况下为 +、*、-、/）。对于给定的顶级节点，根据顶级节点左侧的叶子数量组织搜索，该数量必须是 1 到 3 范围内的数字。有一个自然的递归解决方案，例如，如果左边有三片叶子那么它本身就是一棵三片叶子的二叉表达式树。你真的不需要使用树数据结构 - 你可以使用完全括号字符串（例如像“（（（1 + 2）* 3）/ 4）”对于顶部节点是“/”的树，它的左边side 是树 "((1 + 2)*3)" 右边是叶子 4).
实际上要检查的组合并不多，因为优先案例的数量限制为 5:
((a:b):c):d
(a:b):(c:d)
(a:(b:c)):d
a:((b:c):d)
a:(b:(c:d))
因此，从 4 种可能的运算符中进行 24 种排列和 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>");
这是一个更简单的解决方案，没有优先级数组。它有单独写出的五个优先案例的计算。通常程序员会认为这是一个不优雅的解决方案，因为它违反了 "don't repeat yourself" 规则；然而，在这种情况下，它使代码更容易理解，并且大大简化了结果的显示，所以我认为这样做是有道理的。
这个版本只有 returns 每个数字排列和运算符组合的解决方案，因为括号位置不同的解决方案，如 (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>");