【老码农带带我】论非酋的自我修养

-回复 -浏览
楼主 2018-12-05 14:41:40
举报 只看此人 收藏本贴 楼主

概述

本篇推送介绍了求出在最差情况下的最优解(worst-case scenario)的一个算法,更加通俗的说,就是求出在最倒霉情况下的如何减少损失。


该算法的效率会比二分等方法略高,但是难度也比其他方法略有增加,使用频率可能并不高。


通篇没有使用代码,只涉及到大学前的数学运算,请放心食用。


今天,非酋和欧皇一起做实验;


他们都有两个一样的鸡蛋,面前有一栋100层高的楼。

他们的任务是,测试出扔出鸡蛋,并使鸡蛋不碎掉的最高楼层。(如果鸡蛋在43层才能碎,那么答案就是42)

//鸡蛋没坏掉可以捡回来再扔,而且性质不会发生变化


warning:高空抛物有害健康(他人的)


欧皇的方案十分简单,先随便选择一个楼层n,扔下后如果碎了,那么在(n-1)楼扔必然不会碎;如果没有碎,那么在(n+1)楼扔必然碎;欧皇完成这个操作一共最多需要扔两次鸡蛋。


最简(bao)单(li)解法

非酋一层一层的扔,因为在100层,扔了100次


常规解法

把楼层分为N分,每次从100/N的倍数层扔下鸡蛋,然后再逐层检查某个特定的部分。

假如N=4,则扔鸡蛋的顺序是25层,50层,75层,100层;假如在50层时碎掉,再从25-50开始递推。

这样最多需要扔28次

//假定解在99/100层,需要扔的层数是25L,50L,75L,100L,76L-99L,共计28层


在做实验之前,非酋分析了自己预期的实验次数和欧皇差距如此之大的原因。

  1. 脸黑

  2. 脸黑

  3. 脸黑


于是非酋列了一个预期实验次数的表(N=4)

非酋专用


预期实验次数(N=4)

假定解所在楼层

所需实验次数

24/25

25

49/50

26

74/75

27

99/100

28

无论是24L还是25L,所需次数都是一样的


如果采取均分的方式,每一个部分都要扔24次鸡蛋才能到达区域的最后一楼,而每进入下一个区域,都需要额外扔一次鸡蛋,于是所需实验次数越到后面越大。

//1-24L和26-49L所需的次数是相同的,但是后者需要额外扔一个50L,这是越到后面所需次数增加的关键原因


为了避免这种情况发生,非酋决定让前面的部分涵盖的楼层数增加,来抵消进入每一个部分时所需要的实验次数

//举一个很简单的例子,如果第一区域的楼层数为25,第二区域只有24,那么解在25层或者49层时所需的实验次数是相同的


均衡解法

为了便于理解,我先假定一个函数,F(n)为第一个鸡蛋第n次做实验时所在的楼层。


预期实验次数

假定解所在楼层

所需实验次数

F(1)

F(1)

F(2)

F(2)-F(1)+1

F(3)

F(3)-F(2)+2

……

……

F(n)

F(n)-F(n-1)+n-1

为了简洁,这里不再列出F(n)-1之类的解


那么,非酋最后的预期实验次数就是

max( F(1), F(2)-F(1)+1,…, F(n)-F(n-1)+n-1 )

//对于解在F(n)的情况,首先要从F(1)扔到F(n),计n次,然后从F(n-1)+1实验到F(n)-1,计F(n)-F(n-1)-1 次实验,共计F(n)-F(n-1)+n-1次实验


如果令每个部分的楼层数为D(n),可以得到

max( D(1), D(2)+1, D(3)+2,…D(n)+n-1 )

//很明显,D(n)=F(n)-F(n-1),如F(2)=20,F(1)=10时,第二个区域的楼层数为11-20L,共20-10=10层。


非酋想让每一个元素的值都尽量接近,这样他的期望实验次数才会最小,那么D(n)应当为一个等差序列,公差为-1。同时,D(1)+D(2)+…+D(n)应当大于等于100

//每部分的楼层之和要大于总楼层数


D(n)的最小值是1,所以不等式等价于(n+1)n/2 >= 100;

//由常识,楼层数应该大于0


易得n=14,此时总和达到了105。F(n)的值可以从100开始倒推,也可以从1开始正推,会得出不同的结论


至此,非酋成功把实验次数压到了14次,相比最开始的100次有了质的飞跃!

//由此可见,欧皇是多么的可恶


这是一个可能的解:

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 


预期实验次数

解所在楼层

所需实验次数

14

14

39

14

77

14

99

14

100

12


传送门(英文):http://poj.org/problem?id=3783

对这道题目有兴趣的同学可以进入传送门


——谨以此推送悼念死于实验器材的小编

非欧分界线


文案:周洲游

排版:周洲游

责任编辑:龙灏天

软件学院团委宣传部出品


我要推荐
转发到