24点

May 07, 2018

题目

从 1~13 任取四个数字，通过+，-，* ，/和() 来计算 24 点

其实这个是算法分析里面提到过的一个标准做法，使用的方式是逆波兰表达式，也就是后缀表达式 首先把全部运算情况的逆波兰表达式穷举出来，采用逆波兰表达式是因为不用考虑操作符的优先级. 24 点的逆波兰表达式总共有如下 4 种情况. 其中 abc 的代表 4 个数字 #代表+-*/任意一个操作符.

ab#cd##
abc##d#
abcd###
ab#c#d#

后面就是遍历这四个数字的全排列和操作符的全排列即可，其中数字不可以重复使用，操作符可以重复使用

代码

function calculate(a, b, operator) {
  switch (operator) {
    case "+":
      return a + b
    case "-":
      return a - b
    case "*":
      return a * b
    case "/":
      return b === 0 ? -10 : a / b
    default:
      return -10
  }
}

function equalTo24(...nums) {
  let result = 0,
    result1 = 0
  const operators = ["+", "-", "*", "/"]

  for (let i1 = 0; i1 < 4; i1++) {
    for (let i2 = 0; i2 < 4; i2++) {
      if (i1 === i2) continue
      for (let i3 = 0; i3 < 4; i3++) {
        if (i3 === i1 || i3 === i2) continue
        let i4 = 6 - i1 - i2 - i3
        for (let o1 = 0; o1 < 4; o1++) {
          for (let o2 = 0; o2 < 4; o2++) {
            for (let o3 = 0; o3 < 4; o3++) {
              // ab#cd##
              result = calculate(nums[i1], nums[i2], operators[o1])
              result1 = calculate(nums[i3], nums[i4], operators[o2])
              result = calculate(result, result1, operators[o3])
              if (result === 24)
                return `(${nums[i1]}${operators[o1]}${nums[i2]})${operators[o3]}(${nums[i3]}${operators[o2]}${nums[i4]})`
              // abc##d#
              result = calculate(nums[i2], nums[i3], operators[o1])
              result = calculate(nums[i1], result, operators[o2])
              result = calculate(result, nums[i4], operators[o3])
              if (result === 24)
                return `(${nums[i1]}${operators[o2]}(${nums[i2]}${operators[o1]}${nums[i3]}))${operators[o3]}${nums[i4]}`
              // abcd###
              result = calculate(nums[i3], nums[i4], operators[o1])
              result = calculate(nums[i2], result, operators[o2])
              result = calculate(nums[i1], result, operators[o3])
              if (result === 24)
                return `${nums[i1]}${operators[o3]}(${nums[i2]}${operators[o2]}(${nums[i3]}${operators[o1]}${nums[i4]}))`
              // ab#c#d#
              result = calculate(nums[i1], nums[i2], operators[o1])
              result = calculate(result, nums[i3], operators[o2])
              result = calculate(result, nums[i4], operators[o3])
              if (result === 24)
                return `((${nums[i1]}${operators[o1]}${nums[i2]})${operators[o2]}${nums[i3]})${operators[o3]}${nums[i4]}`
            }
          }
        }
      }
    }
  }
  return "It's not possible!"
}
阅读量

目录