写点什么

一文让你学会如何用代码判断 "24" 点

2020 年 3 月 26 日

一文让你学会如何用代码判断"24"点

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


话不多说,直接看题。


题目:你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。


示例 1:

输入: [4, 1, 8, 7]

输出: True

解释: (8-4) * (7-1) = 24

示例 2:

输入: [1, 2, 1, 2]

输出: False


注意


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

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

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


题目分析

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


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


我们首先定义个方法,用来判断两个数的的所有操作符组合是否可以得到 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 }
复制代码


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


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


举个例子:


func main() {    var a float64    var b float64    b = 2.0    //math.Sqrt:开平方根    c := math.Sqrt(2)    a = b - c*c    fmt.Println(a == 0)                  //false    fmt.Println(a < 1e-6 && a > -(1e-6)) //true}
复制代码


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


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


 //go语言 //judgePoint24_2:判断两个数的所有操作符组合是否可以得到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) }
复制代码


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


//硬核代码,不服来辩!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)}
复制代码


好了。三个数的也出来了,我们再加一个判断 4 个数为 24 点的方法:(排列组合,我想大家都会…)


前方高能!!!


前方高能!!!


前方高能!!!


//硬核代码,不服来辩!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 语言示例

搞定收工,我们整合全部代码如下:


//硬核编程...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)}
复制代码


由于代码过于硬核,


我们直接击败 100%的对手:


(没想到吧!代码还可以这么写~)



本期的题目应该都能看懂吗?


大家还有其他的方法来得到答案吗?


评论区留下你的想法吧!


小浩:宜信科技中心攻城狮一枚,热爱算法,热爱学习,不拘泥于枯燥编程代码,更喜欢用轻松方式把问题简单阐述,希望喜欢的小伙伴可以多多关注!

原文首发于:「小浩算法」


2020 年 3 月 26 日 18:59222

评论

发布
暂无评论
发现更多内容

week4-典型大型互联网应用系统使用技术方案和手段

暖丶冬

架构 0 期 -week3- 命题作业

陈俊

极客大学架构师训练营

【架构师训练营】week 4 homework

eazonshaw

极客大学架构师训练营

【架构师训练营】第四期作业

云064

一个典型的大型互联网应用系统使用了哪些技术方案和手段

张瑞浩

第四周作业

倪惠华

互联网系统应用的技术方案

王麒宇

互联网应用的架构演进

南宫煌

极客大学架构师训练营

第四周总结

Thrine

大型网站架构分析

Lane

极客大学架构师训练营

week04总结

uangguan

架构师训练营第四周 - 总结

Eric

极客大学架构师训练营

架构师训练营-W4-20200701

丁亚宁

极客大学架构师训练营 week4

架构师训练营-第四周-命题作业

sljoai

极客大学架构师训练营 第四周作业

大型网站架构问题

新世界

homework week4

东哥

第4周 系统架构:系统架构知识是架构师的常识而不是能力

陆不得

架构 0 期 -week3- 学习总结

陈俊

极客大学架构师训练营

架构师训练营 week4 - 学习总结

devfan

架构师训练营第四周作业

养乐多

第 4 周 - 学习总结

大海

第四周总结

LEAF

架构师训练营 -week4- 学习总结

暖丶冬

第04周 设计系统架构 学习总结

Jaye

我所接触的大型互联网系统

张瑞浩

第 4 周 - 课后作业

大海

架构师训练营 -W4-20200701-学习总结

丁亚宁

学习 极客大学架构师训练营 week4

架构师训练营week4作业1

平淡人生

week4-作业

a晖

架构师训练营 第四周 作业

极客

架构师训练营 week4

devfan

一文让你学会如何用代码判断&#34;24&#34;点-InfoQ