小编典典

两个鸡蛋问题的困惑

algorithm

两蛋问题:

  • 您将得到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滴。

那么问题出在哪里呢?


阅读 297

收藏
2020-07-28

共1个答案

小编典典

您似乎在假设分段大小相等。为了获得最佳解决方案,如果第一个段的大小为N,则第二个段的大小必须为N-1,依此类推(因为当您开始测试第二个段时,您已经在第一个段上放了一次鸡蛋了)分割)。

2020-07-28