algorithm - 5个数字等于23

Question

如何检查给定的 5 个数字和数学运算(+、-、*)是否可以得到 23 的结果？

例如:

1 1 1 1 1 –– 不可能

1 2 3 4 5 –– 可能

规范:

所有操作都具有相同的优先级并从左到右执行(不是按照数学上正确的顺序)。

Answer 1

虽然您可以使用蛮力来尝试所有可能的组合，但我会建议一个稍微更优雅的解决方案:

最后一位和乘法是关键。如果结果 (23) 不能被最后一位数整除，则最后一个运算符不能是“*”。然后你可以尝试相同的结果 + - 最后一位数字，因为它被添加或减去。以这种方式向后迭代应该可以节省相当多的迭代次数。

伪代码示例:

var digits = [1, 2, 3, 4, 5];
var expected = 23;
var combinatoric =  function(digits, expected) {
    var result = false;
    var digit = digits[digits.length -1];
    var nDigits = digits.removeLast();
    // If we are at the last digit...
    if(nDigits.isEmpty() && Math.abs(digit) == Math.abs(expected)) {
        //Last digit must be added or substracted, as its the starting digit.
        result = true;
    } else if(!nDigits.isEmpty()) {
        //Only if divisible is "*" an option.
        if(expected % digit == 0) {
            if(combinatoric(nDigits, expected / digit) {
                result = true;
            }
        }
        // "+" and "-" are always options.
        if(combinatoric(nDigits, expected - digit) {
            result = true;
        }
        if(combinatoric(nDigits, expected + digit) {
            result = true;
        }
    }
    return result;
}

这种方法至少可以节省几次迭代，因为如果无论如何都无法解析为自然数，您就不会尝试乘法。通过倒退，您可以使此计算递归，因为修改后的预期结果会传递到每次迭代。