Menu
This is exercise problem 1.4.24 from Robert Sedgewick's Algorithms 4th Edition.
Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.
While the lgN solution is easy to think up, I totally have no idea about the 2lgF solution. Anyway, we are not given the value of F, so where the ground of 2lgF solution is?
Can anyone give some light on this question? Thanks.
295
To drop an egg without breaking it, wrap the egg in wet paper towels and place it in a plastic bag of puff rice cereal. Fill 4 small bags with puffed cereal too, then put all the bags into 1 large container. You can also wrap the egg in packing material, like bubble wrap, packing peanuts, or inflated plastic packets.
Dropping and breaking an egg is an announcement of good news. But when the egg is not damaged, or only crack it is considered a bad luck. If you drop the spoon - expect the guest. If you drop the fork - a guest will be a woman.
Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 100 droppings.
A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking. If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.
logN: start at the top, always cut search space in half -> binary search
2 * logF start at 1, next 2, 4, 8 (i.e., 2^i), once the egg breaks (after log F steps) do binary search in the smaller search space (range < F and hence number of searches < log F) --> exponential search
182
The lg(F) solution is to do 1, 2, 4, 8, ... until the first egg breaks at 2^(k+1), then do a binary search in the range 2^K to 2^(k+1).
Another alternative is to carry out the same process until the first egg breaks at 2^(k+1) then start over except adding 2^k to each height: 2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, .... You can keep repeating this process to keep reducing the size of the range you do exponential search in.
5
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
