24点游戏（679）

“24点”是一种数学游戏，正如象棋、围棋一样是一种人们喜闻乐见的娱乐活动。它始于何年何月已无从考究，但它以自己独具的数学魅力和丰富的内涵正逐渐被越来越多的人们所接受。今天就为大家分享一道关于“24点”的算法题目。


话不多说，直接看题。

01、题目分析

第679题：24点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通 *，/，+，-，(，) 的运算得到 24 。

示例 1:

  1. 输入: [4, 1, 8, 7]
  2. 输出: True
  3. 解释: (8-4) * (7-1) = 24

示例 2:

  1. 输入: [1, 2, 1, 2]
  2. 输出: False

注意:

​ 1、除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。

​ 2、每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。

​ 3、你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。


02、题目分析

拿到题目，第一反应就可以想到暴力求解。如果我们要判断给出的4张牌是否可以通过组合得到24，那我们只需找出所有的可组合的方式进行遍历。


4个数字，3个操作符，外加括号，基本目测就能想到组合数不会大到超出边界。所以，我们只要把他们统统列出来，不就可以进行求解了吗？说干就干！


我们首先定义个方法，用来判断两个数的的所有操作符组合是否可以得到24。

  1. func judgePoint24_2(a, b float64) bool {
  2.     return a+b == 24 || a*b == 24 || a-b == 24 || b-a == 24 || a/b == 24 || b/a == 24 
  3. }

但是这个方法写的正确吗？其实不对！因为在计算机中，实数在计算和存储过程中会有一些微小的误差，对于一些与零作比较的语句来说，有时会因误差而导致原本是等于零但结果却小于或大于零之类的情况发生，所以常用一个很小的数 1e-6 代替 0，进行判读！


(1e-6：表示1乘以10的负6次方。Math.abs(x)<1e-6 其实相当于x==0。1e-6(也就是0.000001)叫做epslon，用来抵消浮点运算中因为误差造成的相等无法判断的情况。这个知识点需要掌握！)


举个例子：

  1. func main() { 
  2.     var a float64 
  3.     var b float64 
  4.     b = 2.0 
  5.     //math.Sqrt：开平方根 
  6.     c := math.Sqrt(2) 
  7.     a = b - c*c 
  8.     fmt.Println(a == 0)                  //false 
  9.     fmt.Println(a < 1e-6 && a > -(1e-6)) //true
  10. }

这里直接用 a==0 就会得到false，但是通过 a < 1e-6 && a > -(1e-6) 却可以进行准确的判断。


所以我们将上面的方法改写：

  1. //go语言 
  2. //judgePoint24_2：判断两个数的所有操作符组合是否可以得到24 func judgePoint24_2(a, b float64) bool { 
  3.     return (a+b < 24+1e-6 && a+b > 24-1e-6) || 
  4.         (a*b < 24+1e-6 && a*b > 24-1e-6) || 
  5.         (a-b < 24+1e-6 && a-b > 24-1e-6) || 
  6.         (b-a < 24+1e-6 && b-a > 24-1e-6) || 
  7.         (a/b < 24+1e-6 && a/b > 24-1e-6) || 
  8.         (b/a < 24+1e-6 && b/a > 24-1e-6) 
  9. }

完善了通过两个数来判断是否可以得到24的方法，现在我们加一个判断三个数是否可以得到24的方法。

  1. //硬核代码，不服来辩！ 
  2. func judgePoint24_3(a, b, c float64) bool { 3
  3.     return judgePoint24_2(a+b, c) || 
  4.         judgePoint24_2(a-b, c) || 
  5.         judgePoint24_2(a*b, c) || 
  6.         judgePoint24_2(a/b, c) || 
  7.         judgePoint24_2(b-a, c) || 
  8.         judgePoint24_2(b/a, c) ||          
  9.         judgePoint24_2(a+c, b) ||
  10.         judgePoint24_2(a-c, b) ||
  11.         judgePoint24_2(a*c, b) ||
  12.         judgePoint24_2(a/c, b) ||
  13.         judgePoint24_2(c-a, b) ||
  14.         judgePoint24_2(c/a, b) ||
  15.         judgePoint24_2(c+b, a) ||
  16.         judgePoint24_2(c-b, a) ||
  17.         judgePoint24_2(c*b, a) ||
  18.         judgePoint24_2(c/b, a) ||
  19.         judgePoint24_2(b-c, a) ||
  20.         judgePoint24_2(b/c, a)
  21. }

好了。三个数的也出来了，我们再加一个判断4个数为24点的方法：（排列组合，我想大家都会….）

  1. //硬核代码，不服来辩！
  2. func judgePoint24(nums []int) bool {
  3.     return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  4.         judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  5.         judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  6.         judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  7.         judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
  8.         judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
  10.         judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  11.         judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  12.         judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  13.         judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  14.         judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
  15.         judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
  17.         judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  18.         judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  19.         judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  20.         judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  21.         judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
  22.         judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
  24.         judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  25.         judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  26.         judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  27.         judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  28.         judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
  29.         judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
  31.         judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  32.         judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  33.         judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  34.         judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  35.         judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
  36.         judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
  38.         judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  39.         judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  40.         judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  41.         judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  42.         judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
  43.         judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
  44. }

03、Go语言示例

我们整合全部代码如下：

  1. func judgePoint24(nums []int) bool {
  2.     return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  3.         judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  4.         judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  5.         judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) ||
  6.         judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
  7.         judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) ||
  9.         judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  10.         judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  11.         judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  12.         judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) ||
  13.         judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
  14.         judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) ||
  16.         judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  17.         judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  18.         judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  19.         judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) ||
  20.         judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
  21.         judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) ||
  23.         judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  24.         judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  25.         judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  26.         judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) ||
  27.         judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
  28.         judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) ||
  30.         judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  31.         judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  32.         judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  33.         judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) ||
  34.         judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
  35.         judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) ||
  37.         judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  38.         judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  39.         judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  40.         judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) ||
  41.         judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) ||
  42.         judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0]))
  43. }
  45. func judgePoint24_3(a, b, c float64) bool {
  46.     return judgePoint24_2(a+b, c) ||
  47.         judgePoint24_2(a-b, c) ||
  48.         judgePoint24_2(a*b, c) ||
  49.         judgePoint24_2(a/b, c) ||
  50.         judgePoint24_2(b-a, c) ||
  51.         judgePoint24_2(b/a, c) ||
  53.         judgePoint24_2(a+c, b) ||
  54.         judgePoint24_2(a-c, b) ||
  55.         judgePoint24_2(a*c, b) ||
  56.         judgePoint24_2(a/c, b) ||
  57.         judgePoint24_2(c-a, b) ||
  58.         judgePoint24_2(c/a, b) ||
  60.         judgePoint24_2(c+b, a) ||
  61.         judgePoint24_2(c-b, a) ||
  62.         judgePoint24_2(c*b, a) ||
  63.         judgePoint24_2(c/b, a) ||
  64.         judgePoint24_2(b-c, a) ||
  65.         judgePoint24_2(b/c, a)
  66. }
  68. func judgePoint24_2(a, b float64) bool {
  69.     return (a+b < 24+1e-6 && a+b > 24-1e-6) ||
  70.         (a*b < 24+1e-6 && a*b > 24-1e-6) ||
  71.         (a-b < 24+1e-6 && a-b > 24-1e-6) ||
  72.         (b-a < 24+1e-6 && b-a > 24-1e-6) ||
  73.         (a/b < 24+1e-6 && a/b > 24-1e-6) ||
  74.         (b/a < 24+1e-6 && b/a > 24-1e-6)
  75. }

执行结果：

PNG


由于代码过于硬核，我们直接击败100%的对手：（没想到吧！代码还可以这么写~）