"24 o'clock" is a kind of mathematical game, just like chess and go, it is a kind of entertainment that people like to see. It can't be traced back to when it started, but it is gradually accepted by more and more people with its unique mathematical charm and rich connotation. Today, I'd like to share an algorithm topic about "24 points".
Don't talk much, just look at the questions.
**Title: * * you have 4 cards with numbers from 1 to 9. You need to decide if you can get 24 by *, /, +, -, (,).
Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24
Example 2:
Input: [1, 2, 1, 2]
Output: False
Be careful:
- Division operator / indicates real division, not integer division. For example: 4 / (1 - 2 / 3) = 12.
- Each operator operates on two numbers. In particular, we cannot use - as a unary operator. For example, when [1, 1, 1, 1] is input, the expression - 1 - 1 - 1 is not allowed.
- You can't connect numbers together. For example, when the input is [1, 2, 1, 2], it cannot be written as 12 + 12.
Title Analysis
When you get the question, you can think of violent solution in the first reaction. If we want to determine whether the given four cards can be combined to get 24, then we just need to find out all the composable ways to traverse.
Four numbers, three operators, parentheses, basic visual inspection can think that the number of combinations will not exceed the boundary. So, if we list them all, can't we solve them? Do what you say!
We first define a method to determine whether all operator combinations of two numbers can get 24.
func judgePoint24_2(a, b float64) bool { return a+b == 24 || a*b == 24 || a-b == 24 || b-a == 24 || a/b == 24 || b/a == 24 }
But is this method right? Actually not! Because in the computer, there will be some small errors in the calculation and storage process of real numbers. For some statements compared with zero, sometimes it will lead to the situation that the original value is equal to zero but the result is less than or greater than zero due to the error. Therefore, a very small number 1e-6 is often used instead of 0 for interpretation!
(1e-6: the negative 6th power of 1 times 10. Math. ABS (x) < 1e-6 is actually equivalent to x==0. 1e-6 (i.e. 0.00000 1) is called epslon, which is used to offset the indeterminate equality caused by errors in floating-point operations. This knowledge needs to be mastered! )
for instance:
func main() { var a float64 var b float64 b = 2.0 //math.Sqrt: square root c := math.Sqrt(2) a = b - c*c fmt.Println(a == 0) //false fmt.Println(a < 1e-6 && a > -(1e-6)) //true }
Here, a==0 is used directly to get false, but a < 1e-6 & & a > - (1e-6) can make accurate judgment.
So we rewrite the above method:
//go language //Judge point24: judge whether all operator combinations of two numbers can get 24 func judgePoint24_2(a, b float64) bool { return (a+b < 24+1e-6 && a+b > 24-1e-6) || (a*b < 24+1e-6 && a*b > 24-1e-6) || (a-b < 24+1e-6 && a-b > 24-1e-6) || (b-a < 24+1e-6 && b-a > 24-1e-6) || (a/b < 24+1e-6 && a/b > 24-1e-6) || (b/a < 24+1e-6 && b/a > 24-1e-6) }
We have improved the method of judging whether 24 can be obtained by two numbers. Now we add a method of judging whether 24 can be obtained by three numbers.
//Hard core code, refuse to argue! func judgePoint24_3(a, b, c float64) bool { return judgePoint24_2(a+b, c) || judgePoint24_2(a-b, c) || judgePoint24_2(a*b, c) || judgePoint24_2(a/b, c) || judgePoint24_2(b-a, c) || judgePoint24_2(b/a, c) || judgePoint24_2(a+c, b) || judgePoint24_2(a-c, b) || judgePoint24_2(a*c, b) || judgePoint24_2(a/c, b) || judgePoint24_2(c-a, b) || judgePoint24_2(c/a, b) || judgePoint24_2(c+b, a) || judgePoint24_2(c-b, a) || judgePoint24_2(c*b, a) || judgePoint24_2(c/b, a) || judgePoint24_2(b-c, a) || judgePoint24_2(b/c, a) }
Okay. Three numbers have also come out. Let's add another method to judge four numbers as 24 points: (arrangement and combination, I think everyone will...)
High energy ahead!!!
High energy ahead!!!
High energy ahead!!!
//Hard core code, refuse to argue! func judgePoint24(nums []int) bool { return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0])) }
Go language example
After finishing the work, we integrated all the codes as follows:
//Hard core programming func judgePoint24(nums []int) bool { return judgePoint24_3(float64(nums[0])+float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])-float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])*float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])/float64(nums[1]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[1])-float64(nums[0]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[1])/float64(nums[0]), float64(nums[2]), float64(nums[3])) || judgePoint24_3(float64(nums[0])+float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])-float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])*float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])/float64(nums[2]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[2])-float64(nums[0]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[2])/float64(nums[0]), float64(nums[1]), float64(nums[3])) || judgePoint24_3(float64(nums[0])+float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])-float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])*float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[0])/float64(nums[3]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[3])-float64(nums[0]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[3])/float64(nums[0]), float64(nums[2]), float64(nums[1])) || judgePoint24_3(float64(nums[2])+float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])-float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])*float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[2])/float64(nums[3]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[3])-float64(nums[2]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[3])/float64(nums[2]), float64(nums[0]), float64(nums[1])) || judgePoint24_3(float64(nums[1])+float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])-float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])*float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])/float64(nums[2]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[2])-float64(nums[1]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[2])/float64(nums[1]), float64(nums[0]), float64(nums[3])) || judgePoint24_3(float64(nums[1])+float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])-float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])*float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[1])/float64(nums[3]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[3])-float64(nums[1]), float64(nums[2]), float64(nums[0])) || judgePoint24_3(float64(nums[3])/float64(nums[1]), float64(nums[2]), float64(nums[0])) } func judgePoint24_3(a, b, c float64) bool { return judgePoint24_2(a+b, c) || judgePoint24_2(a-b, c) || judgePoint24_2(a*b, c) || judgePoint24_2(a/b, c) || judgePoint24_2(b-a, c) || judgePoint24_2(b/a, c) || judgePoint24_2(a+c, b) || judgePoint24_2(a-c, b) || judgePoint24_2(a*c, b) || judgePoint24_2(a/c, b) || judgePoint24_2(c-a, b) || judgePoint24_2(c/a, b) || judgePoint24_2(c+b, a) || judgePoint24_2(c-b, a) || judgePoint24_2(c*b, a) || judgePoint24_2(c/b, a) || judgePoint24_2(b-c, a) || judgePoint24_2(b/c, a) } func judgePoint24_2(a, b float64) bool { return (a+b < 24+1e-6 && a+b > 24-1e-6) || (a*b < 24+1e-6 && a*b > 24-1e-6) || (a-b < 24+1e-6 && a-b > 24-1e-6) || (b-a < 24+1e-6 && b-a > 24-1e-6) || (a/b < 24+1e-6 && a/b > 24-1e-6) || (b/a < 24+1e-6 && b/a > 24-1e-6) }
Because the code is too hard core,
We beat 100% directly:
(unexpectedly! The code can also be written in this way ~)
Should all the topics in this issue be understandable?
Do you have any other way to get the answer?
Leave your thoughts in the comment area!
Source: Yixin Institute of Technology
Xiaohao: Yixin science and technology center is a city lion. It loves algorithm, learning, and programming code. It's more like to simply explain the problem in an easy way. I hope that my favorite friends can pay more attention to it!
The original is from "Xiaohao algorithm"