N számú tojás és épület van, amelynek k emelete van. Írjon egy algoritmust annak megállapítására, hogy hány cseppnyi minimális mennyiség szükséges ahhoz, hogy ismerje azt a padlót, ahonnan a tojás leejtése esetén eltörik.
A megoldásom az volt, hogy a padlókat sqrt(k) méretű blokkok csoportjaira bontottam. Például, ha k = 100, akkor ellenőrizni fogom, hogy a tojás eltörik-e a 10., 20., 30....100. emeletről, majd lineáris keresést fogok végezni ebben a blokkban. A megoldás O(sqrt(k)) lesz.
A dinamikus programozási megoldás, amit látok, a következő:
When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.
1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.
k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trials needed to find the critical
floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
x is floors in {1, 2, ..., k}}
Nem tudom, miért használjuk a eggDrop(n, k - x)-t a Floor above x with k-x kiszámításához, mivel k emeletet ad x alatt és nem pontosan X feletti szintet?
Például x = 6-on eggDrop(10, 2) = 1 + min{max(eggDrop(2 - 1, 6 - 1), eggDrop(2, 9 - 6))
Ad,eggDrop(10, 2) = 1 + min{max(eggDrop(1, 5), eggDrop(2, 3))
Az eggDrop(2, 3)) alapvetően egy épület 3 emelettel és 2 tojással, és nem emeletekkel a 6. emelet felett.
Köszönjük!
Forrás: https://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/
