Among n given coins, one of them at most is a bad one. (A bad coin could be eith
ID: 3109977 • Letter: A
Question
Among n given coins, one of them at most is a bad one. (A bad coin could be either heavier or lighter than a good coin.) There is also a supply of coins that are known to be good. We are given a scale balance that lets us compare the total weights of the coins placed on the two sides of the scale balance. We want to design algorithms that determine whether the coins are all good; and if they are not, we want to identify the bad coin and determine whether it is heavier or lighter than a good one. In particular, we will investigate a class of algorithms that allows a three-way branching after each use of the scale balance. That is, depending on whether the total weight of the coins in the left pan of the scale balance is larger than, equal to, or less than the total weight of the coins in the right pan, different courses of action will be followed. The complexity of such algorithms will be measured by the number of times the scale balance is used.
For n = 4, show an algorithm that solves the problem using the scale balance twice. Note that a convenient way to describe the algorithm would be to use a ternary tree in which every internal node represents one use of the scale balance.
Explanation / Answer
Algorithm for N coins:
Find_odd( group 0 of N coin)
1. If N = 1 then print "this is the odd coin " return group 0
1. Devide in [N/3](group 1),[ N/3] (group 2) and (N - 2[N/3])(group 3)
2. compare weigh of group 1 and group 2
if weights are equal then return Find_odd( group 3)
if group 1 > group 2 then
if odd coin weight is higher than normal coin
return Find_odd(group 1)
else
return Find_odd(group 2)
else
if odd coin weight is higher than normal coin
return Find_odd( group 2)
else
return Find_odd( group 1)
==========================================================
complexity of the algorithm O(log3(N)) // log base 3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.