Find the Heavy Ball: suppose you have n metal balls such that n-1 of the balls h
ID: 2075974 • Letter: F
Question
Find the Heavy Ball: suppose you have n metal balls such that n-1 of the balls have exactly the same weight, and one of the balls is slightly heavier (but you can't tell which one is the heavy one). In addition, you have a balance scale: You may put any number of balls onto either cup of the scale and the scale will tell you which side is heavier, or it will tell you that both sides are exactly the same weight. Each measurement you take costs one "scale use". a. Design an efficient algorithm to identify the heavy ball using as few "scale uses" as a possible. Explain why your algorithm is correct and analyze its worst case scale use run time. Be sure to address what to do when n is odd or even. obviously you can solve this problem with n-1 scale uses, so a proper solution should use substantially fewer scale uses. b. consider essentially the same problem as above, but now suppose there are two heavy balls instead of Just one. Design an algorithm to find them and analyze the run time.Explanation / Answer
A.
step 1: count the balls and know whether if even or odd.
step 2: If total count of balls is even place half balls (n/2) on the one side, and other half balls on other side.
else place (n-1)/2 on one side and, remaining half on other side, and keep aside the remaining ball.
Step 3:
if both sides are equal, the heavier ball is left out one, ball is found,Solution found
else ignore the lesser side and take the heavier balls and repeat step 1.
B.
step 1: count the balls and know whether if even or odd.
step 2: If total count of balls is even place half balls (n/2) on the one side, and other half balls on other side.
else place (n-1)/2 on one side and, remaining half on other side, and keep aside the remaining ball.
Step 3:
if both sides are equal, the heavier ball is left out one, repeat the steps and quit when second ball is found.
else ignore the lesser side and take the heavier balls and repeat step 1.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.