两蛋问题:
我相信上面已经提到了两个鸡蛋问题。但是有人可以帮助我理解为什么以下解决方案不是最佳解决方案。
假设我使用具有分段大小的分段和扫描算法s。所以,
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滴。
那么问题出在哪里呢?
您似乎在假设分段大小相等。为了获得最佳解决方案,如果第一个段的大小为N,则第二个段的大小必须为N-1,依此类推(因为当您开始测试第二个段时,您已经在第一个段上放了一次鸡蛋了)分割)。