![\"\"](\"http:\/\/oprsteny.cz\/wp-content\/uploads\/img_51a1f5ebcb258.png\")
Assume you are given 2 eggs.\nYou have access to a 100-floors high building
\nEggs can break if dropped from the first floor or may not even break if dropped from 100th floor.
\nBoth eggs are identical.<\/p>\n
Assume you are given 2 eggs.
\nYou have access to a 100-floors high building
\nEggs can break if dropped from the first floor or may not even break if dropped from 100th floor.
\nBoth eggs are identical.<\/p>\n
You need to figure out the highest floor of a 100-storey building an egg can be dropped from without breaking. The following is a description of the instance of this famous puzzle involving Suppose that we wish to know which floors in a 100-floors high building are safe to drop eggs from, and which will cause the eggs to break on landing. We make a few assumptions: It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 100th-floor windows do not cause an egg to break.<\/p>\n If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way: In the worst case, this method may require 100 droppings.<\/p>\n But according to our scenario we have 2 eggs available. To derive a dynamic programming functional equation for this puzzle, let the state of the dynamic programming model be a pair s = (n,k), where For instance, s = (3,48) indicates that The initial state of the process is s = (N,H) where N denotes the number of test eggs available at start of the experiment. Now, let function\u00a0W(n,k) = minimum number of trials required to identify the value of the critical floor under the worst case scenario given that the process is in state s = (n,k).<\/p>\n Then it can be shown that It is easy to solve this equation iteratively by systematically increasing the values of x.<\/p>\n In the following code there is my own generalized solution for N eggs and K-floors high building coded in C++. I know it’s not optimal, but it works and gives correct results.<\/p>\n Assume you are given 2 eggs. You have access to a 100-floors high building Eggs can break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to … Continue reading
\nThe question is how many drops you need to make. You are allowed to break 2 eggs in the process<\/em><\/p>\n
\n– N = 2 eggs
\n– building with H = 100 floors<\/p>\n
\n– An egg that survives a fall can be used again.
\n– A broken egg must be discarded.
\n– The effect of a fall is the same for all eggs.
\n– If an egg breaks when dropped, then it would break if dropped from a higher window.
\n– If an egg survives a fall, then it would survive a any shorter fall.<\/p>\n
\n1. drop the egg from the first-floor window
\n2. if it survives, drop it from the second-floor window
\n3. Continue upward until it breaks<\/p>\n
\nWhat is the least number of egg-droppings that is guaranteed to work in all cases?<\/p>\n
\nn = number of test eggs available, n = 0, 1, 2, 3, …, N – 1.
\nk = number of (consecutive) floors yet to be tested, k = 0, 1, 2, …, H – 1.<\/p>\n
\n– 3 test eggs are available
\n– 48 (consecutive) floors are yet to be tested<\/p>\n
\nThe process terminates either when
\n– there are no more test eggs (n = 0) or
\n– when k = 0, whichever occurs first.
\nIf termination occurs at state s = (0,k) and k > 0, then the test failed.<\/p>\n
\nW(n,k) = 1 + min{max(W(n – 1, x – 1), W(n,k – x)): x = 1, 2, …, k;}
\nwith knowing that W(n,1) = 1 for all n > 0 and W(1,k) = k for all k.<\/p>\n#include<iostream>\r\n#include<map>\r\n#include<time.h>\r\nusing namespace std;\r\n\r\nstruct Status {\r\n int n; \r\n int k;\r\n bool operator < (const Status& other) const {\r\n return n < other.n ? true : k < other.k;\r\n }\r\n\r\n Status(int n, int k):n(n), k(k){}\r\n};\r\nmap<string, int> W_res;\r\n\r\nint GetMax (int a, int b) {\r\n return a>b?a:b;\r\n}\r\n\r\nint W(Status status, int passed = 0){\r\n\/*\r\n To Avoid computing the same again ->\r\n use precomputed values\r\n*\/\r\n if(W_res.find(status) != W_res.end()) {\r\n return W_res[status];\r\n }\r\n\r\n if(status.n == 0 && status.k > 0) throw \"Wrong way\";\r\n else if(status.n == 1 || status.k <= 1) return status.k;\r\n else {\r\n int min = status.k;\r\n int max_x;\r\n for(int x = 1; x <= status.k; x++) {\r\n try{\r\n int max = GetMax(W(Status(status.n-1, x-1), passed), W(Status(status.n, status.k-x), x));\r\n if(max < min) {\r\n min = max;\r\n max_x = x + passed;\r\n }\r\n }catch (const char* err_msg){;}\/\/ignore this result\r\n }\r\n\r\n W_res[status] = 1 + min; \/\/save as precomputed value\r\n return 1 + min;\r\n }\r\n}\r\n\r\nint main (int argc, char *argv[]) {\r\n cout << \"Please enter number of floors: \";\r\n int NUM_FLOORS = 0;\r\n cin >> NUM_FLOORS;\r\n\r\n cout << \"Please enter number of available eggs: \";\r\n int NUM_EGGS = 0;\r\n cin >> NUM_EGGS;\r\n\r\n clock_t start = clock();\r\n\r\n cout << \"Number of floors: \" << NUM_FLOORS << endl\r\n << \"Number of available eggs: \" << NUM_EGGS << endl << endl\r\n << \"How many attempts do we need at worst case \" << endl\r\n << \"to check the highest floor we can drop an egg from \" << endl\r\n << \"without breaking it: \" << W(Status(NUM_EGGS,NUM_FLOORS)) << endl;\r\n\r\n double duration = double((clock() - start)) \/ CLOCKS_PER_SEC;\r\n cout << \"\\nTime needed for computation (sec): \" << duration \r\n << \"\\n\\nPress Enter to termiate\";\r\n\r\n cin.ignore();\r\n cin.get();\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"