专栏首页Crossin的编程教室友尽妙招:用Python解“智力游戏”

友尽妙招:用Python解“智力游戏”

之前国庆假期在家闲来无事,找了一本“思维训练手册”(其实就是一些智力题、推理题,甚至“脑筋急转弯”),跟家人一起玩智力游戏。这些题是不是真的可以训练人的思维我不知道,但是看了几题我忍不住要吐槽:这真的不是从“青少年信息学奥林匹克”题库里找出来的题吗?!

里面有不少题,让人做是有的烧(wu)脑(liao),但如果改成编程题,那倒有点意思了。

于是,原本拿着纸笔做题的场景,就立马被我改成了拿出电脑敲代码的画风。

我从里面挑了3题,你们感受一下。

如果你像我一样喜(xian)欢(de)挑(wu)战(liao),也可以来试试,不管用不用编程。

答案在文末,另外也附了我的代码解法,欢迎取用。

1.

(答案见文末)

思路提示:

用程序解这类“智力题”有个屡试不爽的方法,就是“枚举法”,或者叫做“暴力解法”。就是对于存在有限种可能选择的情况下,让程序把每一种情况都试一遍,找出符合条件的解。

这题就可以暴力去解。

当然,暴力最好也要有头脑的暴力。比如这里,5个3位数,从中去掉9个数,听上去有点烦。但反过来想,其实不就是从里面挑6个数字嘛!

100、10、1、300、……、90、9,这15个数里面取6个,使得它们的和是1111,这我已经不能再提示了吧!

对了,再说一句:Python里有个取排列/组合的库,叫做:itertools。谁用谁知道

2.

为了方便讨论,我给这些圆圈加上编号:

(答案见文末)

思路提示:

这题,比上一题复杂,因为它的不是一个规则的“形状”。但它的可能性依然是有限,且不是很多。

9个数放进9个格子里,最多也就是9!=362880种情况,这对于计算机来说是个小case。关键在于你如何判断某种情况是符合要求的。

如果你看过“数据结构”有关的书,应该会想到这个结构就是一个“”。我们可以将每个格子定义为一个类,也就是一个节点,每个节点有一个值,还有一个列表,记录它相连其他节点。

判断一个节点是否符合要求,就把它相连节点的值加起来,看看是否与它自己的值所对应的和相等。如果每个节点都符合,那就是我们要的答案。

不过呢,这题还有另一种思路,就是用“递归”去解:

1. 判断 n 个值和 n 个格子是否有解

2. 将一个“不违反条件”的值放入一个格子,然后判断剩下 n-1 个值和 n-1 个格子是否有解,以此类推

3. 如果格子全部放完,即得到答案

4. 如果剩下的值里找不到“不违反条件”的值,则退回上一步,选择下一个值继续

不过就这题来说,递归的条件设定有点复杂,我就不展开细说了,代码里我也给了递归的版本。

特别说明:枚举版本最后遍历了59674种情况,在我的电脑上花了0.18秒“撞”到了答案;而递归版本判断了5320种情况,花了0.015秒。

3.

(答案见文末)

思路提示:

这题就不再适合暴力去解了,因为52个值分到4个盒子里,一共是有4的52次方,也就是20282409603651670423947251286016种情况……

但是仔细想一下,这题也不必暴力。我们只需要把52个值从小到大依次往盒子里放就行。只是放的时候需要判断一下,哪个盒子是“不”能放的,即其中盒子里已有两个数的和等于这个值。如果存在,那么就去下一个盒子,此处不留爷,自有留爷处!(处处不留爷,那一定是题目出错了!)

OK,先就来这3题试试看吧!

讲真,这种题虽然没啥实际意义,但若真要你用代码写出来,也不是那么容易的,很考验你对程序逻辑和数据结构的理解。所以,很多IT公司在招聘开发岗位时也会出一些类似的题,既是考察你分析问题的能力,也能看出你写代码的水平。讲不定哪天你就在面试时碰到我发过的题目呢。(事实上,这种事已经发生过几次了,甚至还有面试官就直接拿我的题目去面人的)

智力题

答案(设置了白色字体,长按下方空白后选中可见。深色模式请自便!):

1.

111

x3x

x7x

9xx

(此题共有5个解,参见代码输出)

2.

按图上圆圈标记顺序:

2, 5, 8, 9, 3, 4, 6, 7, 1

3.

[1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52],

[3, 5, 6, 12, 14, 21, 23, 30, 32, 39, 41, 48, 50],

[8, 9, 11, 15, 18, 35, 36, 38, 42],

[17, 20, 24, 26, 27, 29, 33, 45]

(此题也不是唯一解,比如把48放进盒子4也是可以的)

本文分享自微信公众号 - Crossin的编程教室(crossincode),作者:Crossin先生

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 人生苦短,Python编程要纳入高考从娃娃抓起?

    雨尘
  • 与AI赛跑?麻省理工发布AI指数 称人类常常“错估”人工智能

    原标题:与AI赛跑?麻省理工发布AI指数 称人类常常“错估”人工智能 一份新的报告试图具体衡量人工智能混乱的进展。 ? 人工智能到底有多聪明?进展有多快? 这些...

    企鹅号小编
  • 学习Python最好的途径——激发自己的学习兴趣!

    “人生苦短,我用Python”。这句戏言真实反映了Python语言的江湖地位。那么,要快速上手和进阶Python编程,有什么好途径呢?我推荐游戏开发。

    一墨编程学习
  • 荐号|朋友圈那些有趣有料的订阅号

    大数据文摘
  • 寒冬+裁员,0-1年开发从业者凭什么月薪15K?

    这个世界变化太快,特别是互联网行业。 互联网行业的变化就像一块宝盒,你永远不知道下一次打开跳出来的是什么。 工程师等IT岗位一直是一个香饽饽,人才需求极大,在...

    腾讯NEXT学位
  • 永远的金大侠-人工智能的江湖

    金庸先生已离我们远去,笔者当天在朋友圈看到这一消息时心情非常沉痛。作为在小学时就开始读金庸小说的80后,先生给我们的,不仅仅是一个个鲜活的人物,跌宕起伏的故事情...

    SIGAI学习与实践平台
  • 《The Curious Tale of the Stolen Pets》丨可爱萌宠、妙趣横生的VR旅途游戏

    “我们坐在高高的谷堆上面,听妈妈讲那过去的事情~”在没有手机、电脑、电子游戏的年代里,童年睡前最爱的娱乐活动应该就是听爸爸妈妈讲故事。精彩动人的画中世界随着一句...

    VRPinea
  • Windows7 寿终正寝:那些一并消逝的微软软件你知多少?

    本月,一代经典操作系统微软Windows 7正式迎来了生命周期的完结。微软宣布,此后将不再为Win7提供任何形式的更新,包括安全更新、稳定性更新和功能更新;而仍...

    周三不加班
  • 从打王者荣耀发散思维到网络安全个人谈|FreeBuf专栏

    请慢速阅读一下,我在游戏和网络安全中的发散感悟,这些感悟我觉得我得把它记录下来,怕久了,自己忘记了。 最开始看到这个游戏火起来的时候,是看到身边的同事都在纷纷组...

    FB客服

扫码关注云+社区

领取腾讯云代金券