数值碎碎念(六)——偶尔也放松一下

发表于2018-05-31
评论7 6.1k浏览

偶尔也放松一下。

几年以前,我刚开始研究如何使用Excel的时候,做过一个表格,具体是利用公式加各种判断条件,在五子棋的棋局里选择一个点来落子,基本上是类似五子棋AI的这么一个功能。

当然现在看来太简单了,不过挂出来献个丑也没啥不好,纯放松一下呗。

 

链接: https://pan.baidu.com/s/1gFsvDAYy5abWppQ8xgTlxg 密码: d7qv

 

这篇写得实在太水了我自己都忍不了……再加个小菜好了。

正好前两天有朋友问了我一道题,后来我在网上流传的某大厂笔试题里找到了原题(当然,没有答案……);题目是这样的:

蒸汽列车的速度不慢,经过一夜的旅行,你到达了学院门口,却发现前面是一道61环铁索桥,上面挤满了30只毛草球和30只龙龟(如图中所示)(我要吐槽,朋友并没有给我图!)。毛草球在左侧,他们想到学院里去(到右侧);龙龟在右侧,他们想出来(到左侧)。但他们都不愿给对方让路。行动规则如下:

1)当毛草球(或龙龟)前面的铁环为空时,它可以走过去

2)当毛草球(或龙龟)前面虽然有其它毛草球(或龙龟),但是再前面的铁环为空时,它可以跳过去;

3)毛草球已经非常着急了,第一步要安排毛草球行动;

4)毛草球不能向左走,龙龟不能向右走。

现在,你要安排毛草球和龙龟的各自行动顺序,让他们都能到达对岸。请给出最少的行动步骤数。

 

我跟朋友都用归纳法得到了这样一个结论:如果双方的数目都是n,那么所需步数就是n^2+2*n;但是归纳法的这个结论是否准确?为什么会是这样的一个步数呢?

首先说结论:这个归纳是准确的;如何证明呢?

我当时的思路是这样的:

双方各有n个单位,放在2n+1个格子里,左边是nA,右边是nB;对于每个个体而言,“爬行”1次可以移动1格,“跳跃”1次可以移动2格,也就是说“跳跃”比“爬行”每次行动可以多移动1格;那假设规则里没有“跳跃”和阻挡,那就单纯地把两方交换需要移动多少次呢?很容易知道把A全都移动到右边需要移动n*(n+1)次,所以交换的话就是n*(n+1)*2;但是因为有“跳跃”这个行为,所以可以节约移动次数;那两者交汇期间,总共发生了多少次跳跃呢?因为不能回头,所以对于AB双方而言都是单向的,就是A1跳完B1之后,B1就不能再跳A1了;这种情况下,只考虑AB的情况,也就是说,对于每一个A来说,前面都有nB,所以每个A都可以少跳n次,所以总共就是n*n次,所以总次数就是n*(n+1)*2-n*n=n^2+2n,这样根本不用管移动过程是什么样,直接跳到结果就行了。

恩,灌完水了,我想想下一篇写啥……

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

标签: