Im currently doing a puzzle in my book Algorithhms 4th Edition by Robert Sedgewick and Kevin Wayne, and this puzzle is about the classic Egg Dropping problem.
The book doesn't cover much of it, and Im having a hard time understanding how the logic here works. But, there are three questions in the book that goes kind of like this:
Presume that we have a story building with N-floors, and presume that an egg will break if you drop it from floor F(F ≤ N) or higher, but the egg will NOT break if you drop it from any floor lower than this. We know the value of N, and now we are going to figure out the value of F.
a.) Presume that we have loads of eggs to try this out with. Think of a strategy to figure out F by crushing ∼ lg N eggs.
b.) Improve the strategy by only using ∼ 2 lg F eggs.
c.) Now we presume that we only have one egg. Think of a strategy to figure out the value of F by dropping the egg ∼ F times.
Now my assumption - for the answer of a.) - is that it will take log2(100) ≈ 6,64 eggs/7 egg drops (≈7 eggs) if I where to have 100 floors (cause it's easier to count) using a binary search?! or am I totally wrong?
The b.) answer I don't really understand.
And c.) Will be F = F dropps, since we only have one egg it will be crushed on the "Fth" floor. If the height of the floor we are dropping the egg from, starting at level 0, doesn't break the egg, then we try floor 1, and if the egg doesn't break there either we try floor 2 and so on and so on... It will be a linear search.
Have any of you all come across this type of problem before and what do you make of it? (this is my first semester studying algorithms and data structures, so I'm a novice at this 110%).
Thanks!