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

偶尔也放松一下。

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

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

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

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

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

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

（1）当毛草球（或龙龟）前面的铁环为空时，它可以走过去

（2）当毛草球（或龙龟）前面虽然有其它毛草球（或龙龟），但是再前面的铁环为空时，它可以跳过去；

（3）毛草球已经非常着急了，第一步要安排毛草球行动；

（4）毛草球不能向左走，龙龟不能向右走。

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

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

首先说结论：这个归纳是准确的；如何证明呢？

我当时的思路是这样的：

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

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