用程序解决「2018年刑侦科推理试题」

周五的时候公司群发了这个推理题的图片,周六有同事尝试用python去解这个题,然后大家纷纷产生了兴趣要尝试一把。

用程序去解这个题,首先要判断下问题规模。整个卷子公有10个含有4选项的选择题,所以如果枚举每个可能选项,一共有4^10个,大概是10^6这个规模,比起上Ghz(10^9)的CPU,理应是在毫秒级完成遍历,加上每次还要进行条件判断,枚举解决应该最终时间是在毫秒级到秒级这个范围。所以这么看枚举法非常合适来解决这个问题。

于是首先用暴力枚举法来实现,语言采用C99

然后用mac默认的gcc带O3优化编译,输出结果

看来运行时间在8ms左右。这么看其实结果也不错,因为在很短的时间里就把这个问题解决了,而且代码量比较少。

但是事情还没有结束。公司群里各位同学纷纷开始比拼优化的时间,有同学通过深度优先搜索加剪枝,优化到0ms的执行时间。于是我也打算试试看怎么实现。通过查看这位同学的代码,搞懂了原理:就是在深度优先搜索的过程中,如果在当前分支不满足条件,则不用继续搜索下去。所以按照这个思路,实现了搜索版的代码:

跑了一下,时间的确短了

大概是在1ms左右。看来搜索+剪枝确实比较有效,而且实际代码量没有增加太多。

这样这个问题通过暴力枚举/深度优先搜索+剪枝两种方法解决,还是挺有意思的~

Leave a Comment

为防机器,验证码请直接输入4个数字1

*