algorithm - 两蛋问题混淆

Question

二蛋问题:

• 给你 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 滴来完成。

那么问题出在哪里呢？

Answer 1

您似乎假定了大小相等的段。对于最佳解决方案，如果第一段的大小为 N，则第二段的大小必须为 N-1，依此类推(因为当您开始测试第二段时，您已经为第一段丢了一次鸡蛋段)。