我刚刚读了两个鸡蛋问题:
两个鸡蛋问题
你有两个鸡蛋,可以进入100层高的建筑.两个鸡蛋都是一样的.目的是找出最高的楼层,当从该楼层的窗户掉出一个鸡蛋时,鸡蛋不会破裂.如果一个鸡蛋掉落但没有破裂,它就没有损坏,可以再次掉落.然而,一旦鸡蛋被打破,那就是那个鸡蛋.
如果一个鸡蛋在从地板上掉落时断裂
n,那么它也会从上面的任何一个地板上断裂.如果一个鸡蛋在摔倒后存活下来,那么它会在任何比这更短的摔倒时存活.问题是:您应该采取什么策略来最大限度地减少找到解决方案所需的蛋数量？.(这将是最糟糕的情况,它需要多少滴？)
我一直在跟着"看看我能做三个"部分.作者指出,在第一个鸡蛋破裂后,它会降解成2个鸡蛋问题并且可以递归地解决.
这很好,但是当我使用3个鸡蛋代替2个鸡蛋(第一个鸡蛋)时,我们不想选择更大的步长吗？从哪个楼层扔掉第一个鸡蛋？
有1个鸡蛋,我们必须从1楼开始.
有2个鸡蛋,我们解决n(n+1)/2=k并且向上舍入,n起始楼层在哪里,是楼层k数.
3 ...我在制定配方时遇到了麻烦.
考虑到这一点,用2个鸡蛋,最大滴数等于我们放下第一个鸡蛋的楼层数.例如,有2个鸡蛋和100个楼层,解决方案是14,这意味着我们从第14层丢弃第一个鸡蛋,如果它破裂,我们必须下降13次,对于1-13楼.
有3个鸡蛋,解决方案是9(如图所示).但是我们不想把第一个鸡蛋扔到9号楼,我们可以把它扔得更高,因为我们不需要在它们之间迭代1秒.
如果我们再次从14楼扔掉,然后它就会破裂,那么我们就会递归.现在n(n+1)/2=k在哪里k13 ...但是这给了我们4.815,如果我们ceil和那个并且加上我们之前的下降我们得到6,这比实际解决方案低,所以这里有些错误...
如果我们再次从14楼扔掉,然后它就会破裂,那么我们就会递归.n(n + 1)/ 2 = k其中k现在是13 ...但是这给了我们4.815,如果我们ceil和那个并且加上我们之前的下降我们得到6,这比实际解决方案低,所以这里的东西是错误...
如果没有破坏怎么办？然后你有一个有三层鸡蛋的问题,共有86层,与100层楼的问题相比,可能要少一滴.
假设你从50下降的第一个蛋个楼.如果它破裂,你有一个两个鸡蛋问题,49层,最多需要10滴.因此,这将给你一个11滴的最坏情况(因为如果它不破坏,50层三蛋问题最多需要7滴).
如果你选择了37 个为首次下降地板,如果它打破了,你有一个36楼的两蛋的问题,需要多达8周额外的下降.如果没有破坏,你会留下63层的三蛋问题.你想要解决这个问题最多只有8滴,所以如果下一次掉落打破鸡蛋,剩下的两个鸡蛋问题应该可以解决最多7滴,因此你可以选择最高的第二滴是37 + 28 + 1 = 66,因为28层是最高可以解决的最多7滴和2个鸡蛋.如果鸡蛋没有破裂,你会有一个34层的三蛋问题,剩下7滴.如果蛋中断的是21(6*7/2),剩下的6滴当然可以解决的最高,所以你可以选择地板66 + 21 + 1 = 88.如果鸡蛋没有破裂,你剩下12层6滴,只有两个鸡蛋已经可以吃了.
系统地说,你可以用d滴剂和e鸡蛋来解决最多的楼层数
/ 1, if d == 1
F(e,d) = | d, if e == 1
\ F(e-1,d-1) + 1 + F(e,d-1), if e > 1 and d > 1
如果你只有一滴,你别无选择,只能选择你还不知道鸡蛋没有破裂的最低层.如果它打破了它,你尝试了更高的楼层,你不知道打破鸡蛋的一楼.
如果你只有一个鸡蛋,你必须检查每个楼层,直到鸡蛋破裂或你的水滴用完.
否则,如果第一滴是高于F(e-1,d-1) + 1地板,如果鸡蛋断裂,你可能找不到第一层.如果第一滴是从较低的楼层,d-1如果鸡蛋没有破裂,你不能达到高滴,所以第一滴应该是从地板F(e-1,d-1) + 1.如果它破裂,您可以通过假设解决剩余的e-1蛋和d-1滴.如果没有,您可以F(e,d-1)使用剩余的水滴和鸡蛋来解决下一层楼.
相反,要找到鸡蛋f地板可能需要多少滴e,你必须找到
D(e,f) = min { d | F(e,d) >= f }
你可以通过计算F(e,d)矩阵找到它,或者你可以使用动态编程:
如果您选择s第一滴的地板,如果鸡蛋断裂,您需要最多D(e-1,s-1)下降以确定地板.如果鸡蛋没有破裂,你需要最多D(e,f-s)滴下以确定地板.所以选择s第一滴地板的最坏情况是
WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) }
而最糟糕的情况是
D(e,f) = minimum { WC(s,e,f) | 1 <= s <= f }
(当然在哪里D(e,0) = 0).