so classic problem of finding counterfeit coin among set of coins using weighing balance. completeness, here 1 example of such problem:
a well-known example has 9 (or fewer) items, coins (or balls), identical in weight save one, in example lighter others—a counterfeit (an oddball). difference perceptible weighing them on scale—but coins can weighed. possible isolate counterfeit coin 2 weighings?
we dealing case 1 of coins counterfeit , know how (i.e. know heavier/lighter).
my question is, there general efficient algorithm solve generalized version of problem n coins 1 counterfeit. have been thinking , far have if n of form 3^k, can find counterfeit in ⌈log_3_(n)⌉ splitting them groups of 3 recursively. true n, not jus of 3^k , if so, can better?
unless have information input, ⌈log_3_(n)⌉ best can reach. 3 groups of equal number of coins, weigh 2 of them against each other, , you'll see of 3 groups has lower weight. recursively apply same algorithm lightest group. left-over coins above k^3 kept later rounds.
Comments
Post a Comment