想象一下,你在一座有猫的高楼里.这只猫可以在低矮的故事窗口中摔下来,但如果从高楼层抛出,它就会死亡.你怎么能用最少的尝试数来计算猫可以存活的最长时间？
显然,如果你只有一只猫,那么你只能线性搜索.先从一楼扔猫.如果它存活下来,从第二个扔掉它.最终,从地板f抛出后,猫会死.然后你知道楼层f-1是最大的安全楼层.
但是,如果你有一只以上的猫怎么办？您现在可以尝试某种对数搜索.让我们说这个版本有100层,你有两个相同的猫.如果你将第一只猫从50楼扔出去并且死亡,那么你只需要线性搜索50个楼层.如果您为第一次尝试选择较低楼层,则可以做得更好.假设您选择一次解决20个楼层的问题,并且第一个致命楼层是#50.在这种情况下,你的第一只猫将在从60楼死亡之前从20楼和40楼的飞行中幸存下来.你只需要分别检查楼层41到49.这总共有12次尝试,这比你试图使用二进制消除所需的50次要好得多.
一般来说,对于有2只猫的n层建筑来说,最好的策略和最坏情况的复杂性是什么？n楼和m猫怎么样？
假设所有猫都是等同的:它们都将从给定窗口的摔倒中幸存或死亡.此外,每一次尝试都是独立的:如果一只猫在跌倒时幸存下来,它就完全没有受到伤害.
这不是家庭作业,虽然我可能已经解决了一次学校作业.这只是一个异想天开的问题,今天突然出现在我脑海中,我不记得解决方案了.如果有人知道此问题的名称或解决方案算法的加分点.
language-agnostic algorithm dynamic-programming asymptotic-complexity
我刚刚读了两个鸡蛋问题:
两个鸡蛋问题
你有两个鸡蛋,可以进入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,这比实际解决方案低,所以这里有些错误...