4 ms·
From the text: We now have all the information to compute the optimal two egg solution. While I prefer to read about algorithms and strategies in the fashion
by JeanPierre 14y ago
From the text:
We now have all the information to compute the optimal two egg solution.
While I prefer to read about algorithms and strategies in the fashion the author writes, I'm a bit sad that there's is no proof (or informal reasoning) why this is the optimal solution. Does anyone have a paper or some reasoning which will make me believe that this is the optimal solution?
- tomp 14y agoWhen you break the first egg, the worst case is the difference between the current floor (where the egg broke) and the previous floor (where the egg last survived). So, the worst total number of drops is the number of drops for the first egg (until it breaks), plus the above difference. If you try making the maximum difference less than 14, you run into problems with the first number... The problems with optimizing worst case are much simpler than optimizing the average case (you don't have to deal with probabilities, and you don't need to know the distribution of egg hardness). So, the proof, and the complexity of the proof, depends on what "optimality" measure you choose.