相关疑难解决方法(0)

想象一下,你在一座有猫的高楼里.这只猫可以在低矮的故事窗口中摔下来,但如果从高楼层抛出,它就会死亡.你怎么能用最少的尝试数来计算猫可以存活的最长时间？

显然,如果你只有一只猫,那么你只能线性搜索.先从一楼扔猫.如果它存活下来,从第二个扔掉它.最终,从地板f抛出后,猫会死.然后你知道楼层f-1是最大的安全楼层.

但是,如果你有一只以上的猫怎么办？您现在可以尝试某种对数搜索.让我们说这个版本有100层,你有两个相同的猫.如果你将第一只猫从50楼扔出去并且死亡,那么你只需要线性搜索50个楼层.如果您为第一次尝试选择较低楼层,则可以做得更好.假设您选择一次解决20个楼层的问题,并且第一个致命楼层是#50.在这种情况下,你的第一只猫将在从60楼死亡之前从20楼和40楼的飞行中幸存下来.你只需要分别检查楼层41到49.这总共有12次尝试,这比你试图使用二进制消除所需的50次要好得多.

一般来说,对于有2只猫的n层建筑来说,最好的策略和最坏情况的复杂性是什么？n楼和m猫怎么样？

假设所有猫都是等同的:它们都将从给定窗口的摔倒中幸存或死亡.此外,每一次尝试都是独立的:如果一只猫在跌倒时幸存下来,它就完全没有受到伤害.

这不是家庭作业,虽然我可能已经解决了一次学校作业.这只是一个异想天开的问题,今天突然出现在我脑海中,我不记得解决方案了.如果有人知道此问题的名称或解决方案算法的加分点.

两个鸡蛋问题:

• 给你2个鸡蛋.
• 您可以使用100层高的建筑.
• 鸡蛋可能非常坚硬或非常脆弱意味着如果从一楼掉落可能会破裂,或者如果从100楼掉落则可能甚至不会破裂.两个鸡蛋都是相同的.
• 您需要弄清楚100层高的建筑物的最高楼层,鸡蛋可以在不破坏的情况下掉落.
• 现在的问题是你需要做多少滴.你可以在这个过程中打破2个鸡蛋

我确信已经充分讨论了两个鸡蛋问题(如上所述).但是有人可以帮助我理解为什么以下解决方案不是最佳的.

假设我使用段大小的分段和扫描算法s.所以,

d ( 100 / s   + (s-1) ) = 0    [ this should give the minima,  I need '(s-1)' scans per segment and there are '100/s' segments]
-
ds

=> -100 / s^2 + 1 = 0
=> s^2 = 100
=> s = 10

所以根据这个,我需要最多19滴.但最佳解决方案可以做到14滴.

那么问题出在哪里呢？

它与这个问题有关:两个大理石和一个100层的建筑, 但它不一样......我们要弄清楚最好的算法来弄清楚,最小化找到最低楼层所需的最大跌幅的策略.

这就是我的想法

最后一块大理石必须以逐步的方式掉落

其余的弹珠将选择一跳(比如hop-n)

例如.因此,当N = 2,M = 100时,我们知道最大下降= 14并且第1跳=第一次大理石第一次掉落的地板.