五分之一的死亡游戏 - 第108章 最优思路

    那么，该用什么方法来进行这个步骤的推理呢？
    这个时候，相信屏幕前大部分小可爱们的第一反应都是二分法。
    确实，在所有方法中，二分法解决问题的步骤期望非常不错，看似是个好办法。
    然而，在这个游戏规则的限制下，二分法却是碰都不能去碰的陷阱！
    就拿林朔目前状态来说，他用掉了两条命，只剩下三条命，目前10~99这个区间内的所有东西对他来说都是未知的存在。
    那么，假设答案范围在32~33这两个危险指数之间，由于他起初不知道这个答案，若是贸然采用二分法，将会出现什么情况？
    首先，将这个数字从中间截断，也就是从54开始二分。
    然后，他死了，还剩下两条命。
    那么，接下来呢？
    继续二分，大概就是从32开始。
    然后，又死了，只剩下一条命。
    这个时候，由于机会只剩最后一次，他就不得不从11开始，一步一步往后挪，用这种最原始的蠢办法来确认答案。
    这样一来，时间就成了大麻烦。
    通过前两个步骤，剩余的时间大概只剩下8分钟，也就意味着在这么点儿时间里平均每分钟需要开2~3扇门。然而，光是开门这个动作就需要花费大概20s才能完成，这还不算中途奔波的时间、不算连续开门导致的肌肉疲劳。
    这样一来，最终几乎不可能在规定时间内通关。
    那么，换一种更加保险的方式。不使用二分法，而是采取逐级上跳的办法，先一步确认粗略范围，然后再用一条命来进行细致推理。
    这样可以吗？
    我们来看看。
    比如：首先，选择危险指数为20的房间作为目标，如果没死，就选择危险指数为30的房间作为目标…以此类推。
    假如在选择危险指数为50的房间作为目标后死去，那么接下来就只要从41一个个往上挨个实验，最多到49，即可得到答案。
    表面来看，这似乎是一个不错的办法。虽然它不能像二分法那样快速排除大量错误答案，但却稳扎稳打、一步一个脚印，比较踏实。
    可是，真的是这样吗？
    此处，需要考虑一种极端情况，也就是答案为99~100。
    假设是这样，就意味着玩家需要一直往上推进：20，30，40，50，60，70，80，90,一共8次。
    直到这个时候，才意识到答案在90~100之间。
    在这个游戏中，房间危险指数逐级增高、呈龙摆尾式排列，意味着玩家中途需要花费大量时间赶路——从一头跑到另一头，对时间和体力都是损耗。
    并且，后续还要逐级向上：91，92，93，94，95，96，97，98，99,一共9次。
    直到这个时候，才意识到原来答案是99~100。
    也就是说，如果采用这个方式，最多需要尝试9+8=17次，才能得到确切答案。
    并且，这17次中的8次还需要大量奔波，这将导致时间变得异常紧张。
    毕竟完成不了挑战就得死，林朔当然不可能赌正确答案就在11~20之间，他必须要考虑到最坏情况，这是对自己的生命负责。
    好了！这个时候，相信屏幕前的大聪明、大漂亮们都开窍了，想到了一种更巧妙的办法来完成游戏——
    将第一个二分法和第二个等差递增法结合起来，就可以更加高效地得到正确答案！
    首先，用二分法将数据两份，确定一个大致范围。
    如果死了，就证明正确答案在10~54之间；如果没死，就证明正确答案在55~100之间。
    由于二者等价，所以这里就拿前一种情况举例子。
    确定了这样一个范围后，就沿用方法二的思路，从低到高递增，也就是20、30、40……
    在这种情况下，哪怕遇到极端情况，也就是正确答案为48~49（即玩家在49层死亡），也只需要尝试：
    54 — 1次。
    20，30，40，50 — 4次。
    41，42，43，44，45，46，47，48，49 — 9次。
    总共：1+4+9=14次。
    相比于之前的17次，14次显然已经在这个基础上有了很大提升。这样一来，玩家也不需要那么频繁地奔跑，也就是赶路过程不会再耗费过多时间。
    显然，如果采用这个办法，哪怕遇到了最麻烦的情况，只要手脚足够麻利，应该也能卡点或者接近卡点地成功存活、通关游戏。
    对于大部分玩家而言，想到这一层差不多也就是极限了。
    毕竟时间不等人，必须要尽快行动起来。
    如果还要贪图最后的奖励、再多磨蹭一会儿的话，搞不好连这个办法都行不通了。
    然而，也就在考虑到这个办法的同时，林朔和屏幕前最最聪明的你想到了一个与这种解决方案相似、却又更加特殊、更加巧妙的办法！
    如果要用一句话来形容这个方法，那便是：
    逐级递增，等差递减。
    第一步，和方案三一致，同样是通过二分法先确定一次范围。
    但第二步，却有所不同。
    在方案三中，选择的破题方式为每间隔10个数就进行一次测试，但在林朔所选择的方案四中，这个间隔数却随时发生着改变：
    19，27，24，40，45，49，52
    也就是说，第一次选择的间隔为9（10+9），第二次选择的间隔为8（19+8），第三次选择的间隔为7（27+7）……以此类推，每往上走一步，间隔数字就减少一个。
    让我们来看看这样做的好处。
    假设在19的时候死了，接下来就需要挨个尝试10~19之间的房间，最坏情况下需要尝试11，12，13，14，15，16，17，18，一共8次，加上先前的54，19，一共8+2=10次，解决问题。
    假设在27的时候死了，接下来就需要挨个尝试19~27之间的房间，最坏情况下需要尝试20，21，22，23，24，25，26，一共7次。加上先前的54，19和27，一共7+3=10次，解决问题。
    ……
    假设在52的时候还没死，那么直接可以确定答案为53~54。总共尝试次数为：54，19，27，34，40，45，49，52，一共只需8次。
    发现了吗？
    没错，用这种方法，不管正确答案位于哪个区间，哪怕是最坏情况，最多也只需要花费10次就能解决问题！
    目前还剩下10分钟，哪怕真的遇到最坏情况，平均1分钟也只需要开一扇门，时间绝对足够，甚至绰绰有余！
    （明后两天都加班估计五点多就要起床会很忙。更新尽量更，就是可能晚点发，见谅）