Can i get complete solution for this problem please its from my Algorithms and C
ID: 3743641 • Letter: C
Question
Can i get complete solution for this problem please its from my Algorithms and Complexity class.
The Glass Jar problem You are doing stress-testing on some kind of glass jars to determine the height from which they can be dropped and still not break. Here is the setup. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of this jar and not break. We call this the highest safe rung. Obviously, if a jar is not broken in a throwing, it can be reused; otherwise, you have to use a new jar. Now you are only given K (identical) jars. For simplicity, supoose K = 2 (i.e. you only have two copies of the glass jar). Of course, you can take the simplest way: try throwing one jar from the lowest rung and move one rung up if it does not break. But in the worst case you may need to throw n times, which seems to be not so optimal (note you only use one jar in this case). So our goal is to throw as few times as possible while only using at most K = 2 jars. Now your task: describe a strategy for finding the highest safe rung that only uses K = 2 jars and also minimizes the number of throws in the worst case. Also tell me what is the smallest number of throws you need for the n = 100 case (i.e. 100 rungs) 1
Explanation / Answer
Better strategy here would be to use a binary search technique of sorts. You start fom the middle element, compare its value with the key and move in two possible directions depending upon how the value of the key stacked up against the value of the element.
Going by the same strategy we start from the n/2th rung and make our way up/down depending on how the jar performs in the drop test.
Let us suppose there are 100 rungs and 2 jars.
Start from 50 and drop. Jar breaks(worst case)
Drop from 25. Jar breaks again.
We used up our two jars.
Let us take another case , slightly better than the first one.
Does not break at 50.
So we try at 75. Breaks.
now we try at (50+75)/2 ie. 63 .Survives.
now we try at (63+75)/2 ie. 69. Survives.
Now we try at (69+75)/2 . And so on.