Abo

睿智游戏合集 😶

某种意义上算是有趣的「脑筋急转弯」题目,可以使用算法编程解决,但只要稍加思考,就能找到规律


wallhaven-mdow68

主要介绍Nim游戏的衍生

Nim 游戏

游戏规则是这样的:你和你的朋友面前有一堆石子,你们轮流拿,一次至少拿一颗,最多拿三颗,谁拿走最后一颗石子谁获胜。

假设你们都很聪明,由你第一个开始拿,请你写一个算法,输入一个正整数 n,返回你是否能赢(true 或 false)。

比如现在有 4 颗石子,算法应该返回 false。因为无论你拿 1 颗 2 颗还是 3 颗,对方都能一次性拿完,拿走最后一颗石子,所以你一定会输。

首先,这道题肯定可以使用动态规划,因为显然原问题存在子问题,且子问题存在重复。但是因为你们都很聪明,涉及到你和对手的博弈,动态规划会比较复杂。

我们解决这种问题的思路一般都是反着思考:

如果我能赢,那么最后轮到我取石子的时候必须要剩下 1~3 颗石子,这样我才能一把拿完。

如何营造这样的一个局面呢?显然,如果对手拿的时候只剩 4 颗石子,那么无论他怎么拿,总会剩下 1~3 颗石子,我就能赢。

如何逼迫对手面对 4 颗石子呢?要想办法,让我选择的时候还有 5~7 颗石子,这样的话我就有把握让对方不得不面对 4 颗石子。

如何营造 5~7 颗石子的局面呢?让对手面对 8 颗石子,无论他怎么拿,都会给我剩下 5~7 颗,我就能赢。

这样一直循环下去,我们发现只要踩到 4 的倍数,就落入了圈套,永远逃不出 4 的倍数,而且一定会输。所以这道题的解法非常简单:

1
2
3
4
5
bool canWinNim(int n) {   
// 如果上来就踩到 4 的倍数,那就认输吧
// 否则,可以把对方控制在 4 的倍数,必胜
return n % 4 != 0;
}

PS:其实这个问题是一个简化版的 Nim 游戏,真正的 Nim 游戏比较复杂,不只有一堆石子,不限制一次拿的石子数。但是,这个问题最终的解法却出奇的巧妙,和异或运算有关。文末「阅读原文」链接有一篇详细讲解 Nim 游戏的文章。

石头游戏

见另一篇文章

电灯开关问题

这个问题是这样描述的:有 n 盏电灯,最开始时都是关着的。现在要进行 n 轮操作:

第 1 轮操作是把每一盏电灯的开关按一下(全部打开)。

第 2 轮操作是把每两盏灯的开关按一下(就是按第 2,4,6… 盏灯的开关,它们被关闭)。

第 3 轮操作是把每三盏灯的开关按一下(就是按第 3,6,9… 盏灯的开关,有的被关闭,比如 3,有的被打开,比如 6)…

如此往复,直到第 n 轮,即只按一下第 n 盏灯的开关。

现在给你输入一个正整数 n 代表电灯的个数,问你经过 n 轮操作后,这些电灯有多少盏是亮的?

我们当然可以用一个布尔数组表示这些灯的开关情况,然后模拟这些操作过程,最后去数一下就能出结果。但是这样显得没有灵性,最好的解法是这样的:

1
int bulbSwitch(int n) {    return (int)Math.sqrt(n);}

什么?这个问题跟平方根有什么关系?其实这个解法挺精妙,如果没人告诉你解法,还真不好想明白。

首先,因为电灯一开始都是关闭的,所以某一盏灯最后如果是点亮的,必然要被按奇数次开关。

我们假设只有 6 盏灯,而且我们只看第 6 盏灯。需要进行 6 轮操作对吧,请问对于第 6 盏灯,会被按下几次开关呢?这不难得出,第 1 轮会被按,第 2 轮,第 3 轮,第 6 轮都会被按。

为什么第 1、2、3、6 轮会被按呢?因为 6=1×6=2×3。一般情况下,因子都是成对出现的,也就是说开关被按的次数一般是偶数次。但是有特殊情况,比如说总共有 16 盏灯,那么第 16 盏灯会被按几次?

16=1×16=2×8=4×4

其中因子 4 重复出现,所以第 16 盏灯会被按 5 次,奇数次。现在你应该理解这个问题为什么和平方根有关了吧?

不过,我们不是要算最后有几盏灯亮着吗,这样直接平方根一下是啥意思呢?稍微思考一下就能理解了。

就假设现在总共有 16 盏灯,我们求 16 的平方根,等于 4,这就说明最后会有 4 盏灯亮着,它们分别是第 1×1=1 盏、第 2×2=4 盏、第 3×3=9 盏和第 4×4=16盏。

我们不是想求有多少个可开方的数吗,4 是最大的平方根,那么小于 4 的正整数的平方都是在 1~16 内的,是会被按奇数次开关,最终亮着的灯。

就算有的 n 平方根结果是小数,强转成 int 型,也相当于一个最大整数上界,比这个上界小的所有整数,平方后的索引都是最后亮着的灯的索引。所以说我们直接把平方根转成整数,就是这个问题的答案。

分针时针重合问题

在一天的时间里,钟表的时针和分针会重合多少次?

解析:

答案是22次。

这个问题可以使用编程的方式,具体地求出这22个时针和分针重合的时间都在几点几分。不过,其实只需要稍微想一想,就能想出这个答案:)

大家可以思考一下,在午夜零点的时候,是一天里第一次时针和分针发生重合的时候。下一次在什么时候呢?因为第一分钟,分针就会直接越过时针,所以,在0:00-1:00之间,不可能再发生时针和分针重合的时候了。

下一次时针和分针发生重合的时候,一定是在1点多。具体多少我们可以不求了,但我们知道,1点多一定有一次时针和分针重合的时候。

那么再下一次呢?相信聪明的同学们很快就能想明白,在两点多的位置。

再下一次呢?是三点多。

依此类推。

大家可以思考一下,在时针走回12点之前,最后一次时针和分针重合的时候是什么时候?答案是在十点多,而不是11点多。11:00-11:59这段时间里,时针和分针不会再重合了。分针走过11:00-11:59这一圈的过程中,时针总会比分针更接近12点的位置,直到最后一分钟,时针和分针再次同时指向12点。

因此,在0:00-11:59这12个小时里,时针和分针一共重合了11次。这11次分别是零点;1点多;2点多;3点多;4点多;5点多;6点多;7点多;8点多;9点多;10点多。

那么在一天的时间里,一共24个小时,也就是时针要绕表盘转两圈,所以,一共重合了22次:)

有兴趣的同学可以尝试一下,具体用编程的方式(甚至用数学的方式?)求解一下这22次分别是什么时间:)

电话号码验证问题

你想要检验你的好朋友,同时也是计算机大牛的bobo老师是否知道你的正确的手机号码。

但是,小慕同学不让你接近bobo老师,只给你一张卡片,让你写一个问题给bobo老师。**小慕会将这张卡片传给bobo老师,然后再将bobo老师的回答用这个卡片传回来。这一问一答的过程,你就需要判断出:bobo老师是否知道你的正确的电话号码。**

但是,你并不希望小慕同学知道你的电话号码。**可是,小慕同学一定会偷看你和bobo老师写在卡片上的内容的。**

请问,你要怎么写这张卡片?

解析:

最中规中矩的方法,是使用校验算法(或者摘要算法,哈希算法,不可逆的加密算法,但不管怎样,核心是做校验。)你可以在卡片上写上任意校验算法名称,根据正确的手机号码得到的校验码,以及其他必须的校验信息(如果有的话)。由于bobo老师是计算机大牛,所以可以假设bobo老师可以看懂你写的任何校验算法,然后将他知道的手机号码相应地转换成校验码,和你提供的校验码作比较,之后回答校验成功或者失败就好了。

整个过程,小慕只能看到校验算法相关的信息和校验码,是不能反推出原始信息的。

但是,对于这个问题,其实可以直接在卡片上要求bobo老师根据他所知道的号码给你打一个电话,就能知道bobo老师手上的电话号码是否正确啦!

是不是发现,有些时候,跳出程序员思维,事情会更简单:**)**